multiplied package#

Subpackages#

Module contents#

class multiplied.Algorithm( bits: int, *, matrix: Any = None, saturation: bool = False, dadda: bool = False, )[source]#

Bases: MultipliedMeta

Manages and sequences operations via a series of stages defined by templates and maps.

bits#

The bitwidth of the matrix to be multiplied.

Type:: int

matrix#

The matrix to be multiplied.

Type:: Matrix

dadda#

Whether to use the Dadda-Tree algorithm.

Type:: bool

state#

The current state of the algorithm.

Type:: int

algorithm#

The algorithm to be used.

Type:: dict[int, dict[str, Template | Matrix | Map]]

saturation#

Whether to use saturation arithmetic. Always to original bitwidth.

Type:: bool

auto_resolve_stage(*, recursive=True) → None[source]#

Automatically creates new algorithm stage to reduce the previous stage.

Parameters:: recursive (bool) – Recursively resolve until no partial products remain else resolve a single stage.
Return type:: None

exec( a: int, b: int, ) → dict[int, Matrix][source]#

Run entire algorithm with a single set of inputs then reset internal state.

Parameters:

a (int) – First operand
b (int) – Second operand

Returns:

resultant matrix indexed by stage, including initial state

Return type:

dict[int, Matrix]

push( source: Template | Pattern, map_: Any = None, dadda: bool = False, ) → None[source]#

Populate algorithm stage based on template. Generates pseudo result to represent output matrix

Parameters:

source (Template | Pattern) – The template or pattern to be used for the algorithm stage.
map (Any, optional) – The map to be used for the algorithm stage, by default None
dadda (bool, optional) – Whether to use the Dadda-Tree algorithm, by default False

Return type:

None

Notes

Layout: >>> self.algorithm[x] = { >>> “template” : Template, >>> “pseudo” : Matrix, >>> “map” : Map}

reset( matrix: Matrix, ) → None[source]#: Reset internal state and submit new initial matrix

step() → Matrix[source]#: Execute the next stage of the algorithm and update internal matrix

class multiplied.Map(map: list[Any] | int, *, dadda: bool = False)[source]#

Bases: MultipliedMeta

Generates Map object from row map or standard map.

Each Mapping is defined by a 2-bit hexadecimal value. Positive mappings move bits downwards, negative mappings move bits upwards.

Parameters:: map (list[Any]) – Simplified row map or 2D matrix.

Examples

>>> rmap = [00, FF, FF, 00]
>>> Map(rmap)
[[00,00,00,00,00,00,00,00],
 [FF,FF,FF,FF,FF,FF,FF,FF],
 [FF,FF,FF,FF,FF,FF,FF,FF],
 [00,00,00,00,00,00,00,00]]

build_map(rmap: list[str]) → list[list[str]][source]#

Use row map to generate standard map. Each element of simple map is a 2-bit, signed hex value. +ve = up, -ve = down.

Parameters:: rmap (list[str]) – Row map of the multiplied matrix.
Returns:: Standard map of the multiplied matrix.
Return type:: list[list[str]]

build_zero_map(bits: int) → list[list[str]][source]#: Build a zero map of the specified size.

class multiplied.Matrix( source: list[Any] | int, *, a: int = 0, b: int = 0, )[source]#

Bases: MultipliedMeta

Partial Product Matrix

Parameters:

matrix (list[Any] | int) – A 2D nested list or an integer representing the bitwidth.
a (int=0, optional) – First operand used in partial product generation(PPM)
b (int=0, optional) – Second operand used in PPM

apply_map( map_: Map, *, unified_bounds: dict[str, list[int]] = {}, ) → None[source]#

Use Multiplied Map object to apply mapping to matrix

Parameters:

map (Map) – Map object containing the generated row mapping
bounds (dict[str: list[int]]) – Unified bounds for all arithmetic units

Return type:

None

resolve_rmap( *, ignore_zeros: bool = True, ) → Map[source]#

Find empty rows, create simple map to efficiently pack rows

Parameters:: ignore_zeros (bool) – If True, ignore rows with only zeros
Returns:: Map object containing the generated row mapping
Return type:: Map

class multiplied.Pattern(pattern: list[str])[source]#

Bases: MultipliedMeta

Simplified representation of a Template.

Parameters:: pattern (list[str]) – Pattern to use for the template.

pattern#

Pattern to use for the template.

Type:: list[str]

bits#

Number of bits in the pattern.

Type:: int

get_runs() → list[tuple[int, int, int]][source]#

Returns list of tuples of length, position, and run of a given char in pattern

Examples

>>> Pattern(["A", "A", "A", "B", "B", "B", "B", "C", "C", "C", "C", "C"]).get_runs()
[(3, 0, 3), (4, 3, 4), (5, 7, 5)]

class multiplied.Slice(matrix: list[Any])[source]#

Bases: MultipliedMeta

Matrix slice which adheres to multiplied formatting rules. Retains metadata slice from source object:

Parameters:: matrix (list[Any]) – A slice from any Multiplied object.

class multiplied.Template( source: Pattern | list[list[str]], *, result: list[Any] | Matrix | None = None, matrix: Any = None, )[source]#

Bases: MultipliedMeta

A structure representing collections of arithmetic units using characters. Generated using a partial product matrix and a Pattern or custom template

Parameters:

source (Pattern | list[list[str]]) – The source of the template.
result (list[Any], optional) – The result of the template, by default [], automatically computed
matrix (Any, optional) – The matrix of the template, by default None

build_from_pattern( pattern: Pattern, matrix: Matrix, ) → None[source]#

Build a simple template and it’s result for a given bitwidth based on matrix. Defaults to empty matrix if matrix=None.

Parameters:

pattern (Pattern) – The pattern to build the template from.
matrix (Matrix) – The matrix to build the template from.

Return type:

None

Raises:

ValueError – If the pattern is not a valid Pattern object.

Examples

>>> [matrix] || [pattern] || [templ.] [result]
>>> ____0000 || [  'a',   || ____AaAa __aAaAaA
>>> ___0000_ ||    'a',   || ___AaAa_ ________
>>> __0000__ ||    'b',   || __BbBb__ bBbBbB__
>>> _0000___ ||    'b'  ] || _BbBb___ ________

update_bounding_box( matrix: list[list[str]], ) → dict[str, list[tuple[int, int]]][source]#

Returns dictionary of arithmetic unit and coordinates for their boundaries.

No rigorous inter-row or intra-row boundary checking.

Notes

Bounds are in the form:: {“<unit>”: [(<start>, <end>), …]}

Where (<start>, <end>) are coordinate points in the matrix.

multiplied.allchars( matrix: list[list[str]], *, hash: list[int | bool] = [], ) → set[str][source]#

Returns set of unique characters from a nested list.

Parameters:

matrix (list[list[str]]) – Matrix of characters to extract unique characters from.
hash (list[int | bool], optional) – List of bools or 0s and 1s indicating if a row contains characters.

Return type:

set[str]

Notes

Ignores underscore characters and converts characters to uppercase

See also

Matrix: Multiplied 2D Matrix Object

Examples

>>> allchars([['A', 'B'], ['C', 'D']])
{'A', 'B', 'C', 'D'}

multiplied.apply_complex_map( matrix: list[list[str]], map: Map, unified_bounds: dict, ) → None[source]#

Applies a complex mapping to source Matrix

Parameters:

matrix (mp.Matrix) – Matrix to apply mapping to
map (mp.Map) – Multiplied Map object to apply mapping from
bounds (dict[str: list[int]]) – Unified bounds for all arithmetic units

multiplied.build_adder( char: str, source_slice: Slice, ) → tuple[Slice, Slice][source]#

Create Adder template slice with zero initialised slice and chosen char.

Parameters:

char (str) – The character to use for the template.
source_slice (Slice) – The source slice to use for the template.

Returns:

The template “slices” for addition and the resulting slice.

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [adder-] || [result]
>>> ___0000_ || ___aAaA_ || _aAaAaA_
>>> __0000__ || __AaAa__ || ________

multiplied.build_csa( char: str, source_slice: Slice, ) → tuple[Slice, Slice][source]#

Create CSA template slice with source slice and chosen char.

Parameters:

char (str) – Character to use for the CSA template.
source_slice (Slice) – Source slice object to use for the CSA template.

Returns:

Template “slices” marked for a csa reduction and the resulting slice.

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [csa---] || [result]
>>> ____0000 || ____AaAa || __AaAaAa
>>> ___0000_ || ___aAaA_ || __aAaA__
>>> __0000__ || __AaAa__ || ________

multiplied.build_dadda_map(bits: int) → Map[source]#: Return map representing the starting point of Dadda tree algorithm.

multiplied.build_empty_slice( source_slice: Slice, ) → tuple[Slice, Slice][source]#

Create an empty template slice. Returns template “slices” and resulting slice. Variable length, determined by source slice.

Parameters:: source_slice (Slice) – Source slice to use for the empty template.
Returns:: Tuple of template slices and resulting slice.
Return type:: tuple[Slice, Slice]

Notes

Used for building Templates with large runs of underscore characters. Underscores are used to represent empty spaces in the template.

Examples

>>> [slice-] || [empty-] || [result]
>>> ???????? || ________ || ________
>>> ???????? || ________ || ________
>>> ...      || ...      || ...

multiplied.build_noop( char: str, source_slice: Slice, ) → tuple[Slice, Slice][source]#

Create a No-op template slice with zero initialised slice and chosen char.

Parameters:

char (str) – Character to use for the No-op template.
source_slice (Slice) – Source slice to use for the No-op template.

Returns:

Template “slices” and resulting slice. Target row unaffected

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [noop--] || [result]
>>> ___0000_ || ___aAaA_ || ___aAaA_

multiplied.chargen(start: str = 'A') → Generator[str][source]#

Return Generator characters from A to Z.

Yields:: str

Example

>>> x = chargen()

>>> next(x)
'A'
>>> next(x)
'B'
>>> next(x)
'C'

multiplied.chartff(ch: str) → Generator[str][source]#

Generator to flip flop between upper and lowercase characters.

Parameters:: ch (str) – Single alphabetic character to flip flop.
Yields:: str – Upper or lowercase version of the input character.
Raises:: ValueError – If input is not a single alphabetic character.

Examples

>>> x = chartff('a')
>>> next(x)
'a'
>>> next(x)
'A'
>>> next(x)
'a'

multiplied.df_global_3d_heatmap( path: str, title: str, df: DataFrame, *, dark=False, ) → None[source]#

Export image of 3d plot with heatmap for each stage stacked along the x-axis

Parameters:

path (str) – Path to save the heatmap, ending with a chosen image format.
title (str) – Title of the heatmap.
df (pd.DataFrame) – DataFrame containing the data to be plotted. All available columns are used.
dark (bool, optional) – Whether to use a dark theme for the plot, by default False.

Return type:

None

multiplied.df_global_heatmap( path: str, title: str, df: DataFrame, *, dark=False, ) → None[source]#

Export image of pyplot of global heatmap

Parameters:

path (str) – Path to save the heatmap, ending with a chosen image format.
title (str) – Title of the heatmap.
df (pd.DataFrame) – DataFrame containing the data to be plotted. All available columns are used.
dark (bool, optional) – Whether to use a dark theme for the plot, by default False.

Return type:

None

multiplied.df_stage_bound_heatmap( path: str, df: DataFrame, stages: list[int], bound: list[tuple[int, int]], ) → None[source]#: Export pyplot heatmap of bounding box region across stages

multiplied.df_stage_heatmap( path: str, df: DataFrame, stages: list[int], ) → None[source]#: Export pyplot heatmap for each selected stage

multiplied.empty_map(bits: int) → Map[source]#: Return empty Multiplied Map object

multiplied.empty_rows(matrix: Matrix) → int[source]#: Return the number of empty rows in a matrix

multiplied.export_algorithm( source: Algorithm, path: str, ) → None[source]#: Export multiplied algorithm to JSON file

multiplied.export_parquet( source: DataFrame, path: str, batch_size: int, ) → None[source]#

multiplied.hoist( source: Matrix | Template, *, checksum: list[int] = [], relative: bool = False, ) → Map[source]#

collect bits to the top of the matrix and produce corresponding map.

Parameters:

source (Matrix | Template) – The source matrix or template to hoist.
checksum (list[int], optional) – The checksum to use for hoisting, by default [].
relative (bool, optional) – Whether to use relative coordinates, by default False.

Returns:

The resulting map after hoisting.

Return type:

Map

multiplied.import_algorithm( path: str, ) → Algorithm[source]#: Import multiplied algorithm from JSON file

multiplied.import_parquet( path: str, batch_size: int, ) → Generator[DataFrame][source]#

multiplied.isalpha(ch: str) → bool[source]#: Return True if string is exactly one alphabetic character

multiplied.ischar(ch: str) → bool[source]#: Return True if string is exactly one character

multiplied.ishex2(val: str) → bool[source]#: Return True if string represents a 2-bit hex value

multiplied.isint(source: Any) → bool[source]#: Return True if source converts to int

multiplied.isppm(nested_list: list[list[str]]) → bool[source]#: Return True if nested list represents a Partial Product matrix

multiplied.json_pretty_store( scope: Generator, alg: Algorithm, path: str, ) → None[source]#: Format objects produced by generator then send to JSON file

multiplied.matrix_merge( source: dict[str, Matrix], bounds: dict[str, list[tuple[int, int]]], *, complex: bool = False, ) → Matrix[source]#

Merge multiple matrices into a single matrix using pre calculated bounds

Parameters:

source (dict[str, Matrix]) – A dictionary of matrices to merge
bounds (dict[str, list[tuple[int, int]]]) – A dictionary of bounds for each matrix
complex (bool, optional, default: False) – Performs additional checks during merge

Return type:

Matrix

Examples

>>> source = {'A': Matrix([[1, _], [3, _]]),
              'B': Matrix([[_, 6], [_, 8]])}
>>> bounds = {'A': [(0, 0), (0, 0), (1, 1), (1, 1)],
>>>           'B': [(0, 1), (0, 1), (0, 1), (0, 1)]}
>>> matrix_merge(source, bounds)
Matrix([[1, 6], [4, 8]])

multiplied.matrix_scatter( source: list[list], bounds: dict[str, list[tuple[int, int]]], fmt: str = 'auto', ) → dict[str, list[list]][source]#

Cast matrix subsets to initialised matrix. Each subset based on provided bounds.

Parameters:

source (list[list]) – Partial Product matrix to scatter.
bounds (dict[str, list[tuple[int, int]]]) – The bounds for each unit to extract from the source.
fmt (str, optional, default: "auto".) – “auto” : Infer format from source. “empty” : raw_empty_matrix() “zero” : raw_zero_matrix() “map” : raw_map_matrix()

Returns:

A dictionary of matrices containing the subset of source based on the provided bounds.

Return type:

dict[str, list[list]]

Notes

Each unit is extracted and placed at the same position within an initialised matrix with the same shape as the source.

See also

collect_template_units()

Examples

>>> source = [[0, 1, 2],
>>>           [3, 4, 5],
>>>           [6, 7, 8]]
>>> bounds = {"A": [(0, 0), (0, 1)],
>>>           "B": [(1, 1), (1, 2)]}
>>> matrix_scatter(source, bounds, fmt=empty)
[[[0, 1, _],
  [_, _, _],
  [_, _, _]],
 [[_, _, _],
  [_, 4, 5],
  [_, _, _]]]

multiplied.mprint(matrix: Any)[source]#: Wrapper for print(mp.pretty)

multiplied.pq_extract_bits( path: str, bits: list[int], stages: list[int], ) → DataFrame[source]#: Return a DataFrame of specified bits across multiple stages from .parquet

multiplied.pq_extract_formatted_all(path: str) → DataFrame[source]#: Return DataFrame of all formatted strings from .parquet

multiplied.pq_extract_formatted_stages( path: str, stages: list[int], ) → DataFrame[source]#: Return DataFrame of formatted strings across multiple stages from .parquet

multiplied.pq_extract_stages( path: str, *, stages: list[int] = [], ) → DataFrame[source]#

Return a DataFrame of specified stages from .parquet

Parameters:

path (str) – Path to Multiplied-generated .parquet file
stages (list[int]) – List of stages to extract

Returns:

A subset of the original .parquet table

Return type:

pd.DataFrame

multiplied.pretty(listy_object: Any) → str[source]#

Format Multiplied types, or list as a string.

Parameters:: listy_object (Any) – List or Dict style object to format as a string.
Return type:: str

Examples

>>> pretty(mp.Matrix(4))
____0000
___0000_
__0000__
_0000___

multiplied.raw_dadda_map(bits: int) → list[list[str]][source]#: Returns a Dadda map of size bits.

multiplied.raw_empty_matrix(bits: int) → list[list[str]][source]#

Build an empty partial product matrix for a given bitwidth

Parameters:: bits (int) – The bitwidth of the matrix
Returns:: An empty 2d array for the given bitwidth
Return type:: list[list[str]]

Notes

An empty matrix is completely filled with underscores, following Multipied’s convention

Examples

>>> raw_zero_matrix(4)
[['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_']]

multiplied.raw_empty_row_pos( matrix: list[list[str]], row: int, ) → list[int][source]#: Return positions of empty rows in a raw matrix

multiplied.raw_empty_rows(matrix: list[list[str]]) → int[source]#: Return the number of empty rows in a raw matrix

multiplied.raw_zero_map(bits: int) → list[list[str]][source]#: Returns a zero-filled map of size bits.

multiplied.raw_zero_matrix(bits: int) → list[list[str]][source]#

Build a zero-filled partial product matrix for a given bitwidth

Parameters:: bits (int) – The bitwidth of the matrix
Returns:: A zero-filled 2d array for the given bitwidth
Return type:: list[list[str]]

Notes

A zero matrix is filled with zeros on the diagonal and underscores elsewhere, following Multipied’s convention

Examples

>>> raw_zero_matrix(4)
[['_', '_', '_', '_', '0', '0', '0', '0'],
 ['_', '_', '_', '0', '0', '0', '0', '_'],
 ['_', '_', '0', '0', '0', '0', '_', '_'],
 ['_', '0', '0', '0', '0', '_', '_', '_']]

multiplied.resolve_pattern( matrix: Matrix, ) → Pattern[source]#

For a given matrix, progressively allocate CSAs then adders to pattern

Parameters:: matrix (Matrix) – The matrix to resolve the pattern for.
Returns:: The resolved pattern.
Return type:: Pattern

multiplied.shallow_truth_table( scope: Generator[tuple], alg: Algorithm, ) → Generator[Matrix][source]#: Return Generator of partial product matrices for all operand tuples

multiplied.to_int_matrix(matrix: list[list[str]]) → list[int][source]#

Converts a matrix of characters to a matrix of integers

Parameters:: matrix (list[list[str]]) – Matrix of characters to convert from 2D Multiplied formatted matrix into to list of integers.
Return type:: list[int]

Examples

>>> to_int_matrix([['_', '1', '_'], ['1', '0', '1']])
[2, 5]

multiplied.truth_dataframe( scope: Generator[tuple[int, int]], alg: Algorithm, ) → DataFrame[source]#

Execute algorithm using each pair of operands from the scope.

Parameters:

scope (Generator[tuple[int, int]]) – A generator that yields pairs of integers (a, b) to be used as operands.
alg (Algorithm) – An instance of the Algorithm class representing the algorithm to be executed.

Returns:

A pandas DataFrame containing the truth table for the given algorithm.

Return type:

DataFrame

multiplied.truth_multi_parquet( dir: Path | str, domain_: tuple[int, int], range_: tuple[int, int], alg: Algorithm, workers: int = 4, ) → None[source]#

Generate a truth table and save it to a multi-part Parquet directory.

Parameters:

dir (Path | str) – Directory to store multi-part .parquet files
domain (tuple[int,int]) – The maximum range of values operands a and b can be.
range (tuple[int,int]) – Limit a and b to range_min <= a * b <= range_max
alg (Algorithm) – An instance of the Algorithm class.
workers (int=cpu_count()) – number of .parquet files to create in parallel

multiplied.truth_scope( domain_: tuple[int, int], range_: tuple[int, int], ) → Generator[tuple[int, int]][source]#

Yields (a, b) from domain such that it’s product (ab) lies within range

Parameters:

domain (tuple[int,int]) – The maximum range of values operands a and b can be.
range (tuple[int,int]) – Limit a and b to range_min <= a * b <= range_max

Yields:

tuple – (operand_a, operand_b)

multiplied.truth_table( scope: Generator, alg: Algorithm, ) → Generator[dict][source]#

A generator which yields all stages of an algorithm for a given set of operands a, b.

Parameters:

scope (Generator) – A generator which yields tuples of operands a, b.
alg (Algorithm) – An instance of the Algorithm class.

Returns:

A generator which yields all stages of an algorithm for a given set of operands a, b.

Return type:

Generator[dict]

multiplied.unify_bounds(bounds: dict) → dict[source]#

Returns a simplified bound for non empty characters

Parameters:: bounds (dict) – Bounding box for each arithmetic unit in Template object
Returns:: Unified bounds where {y : [x0, x1]}
Return type:: dict