1
$\begingroup$

I would like to perform multiple 32bit word register additions (mod 32 add. with variables of Boolean type shuffled with symbolic type).

For this task I implemented a ripple adder function:

 (* Ripple addition of 2 Bit Register function *)
sum[a_, b_, c_] := (a && b && c) || (a && ! b && ! c) || (! a && b && ! c) || (! a && ! b && c)
carry[a_, b_, c_] := (a && b) || (a && c) || (b && c)

rippleAdd[x_, y_, cin_] := Module[{r, c},
   Table[Which[i == 1 && j == 1, Subscript[r, i] = BooleanMinimize[sum[x[[i]], y[[i]], cin]],
                i == 1 && j == 2, c = BooleanMinimize[carry[x[[i]], y[[i]], cin]],
                i > 1 && j == 1, Subscript[r, i] = BooleanMinimize[sum[x[[i]], y[[i]], c]],
                i > 1 && j == 2, c = BooleanMinimize[carry[x[[i]], y[[i]], c]]
                ], {i, 1, Length[x]}, {j, 1, 2}];
    Array[Subscript[r, #] &, {Length[x]}]
   ];

This does work quite well if I feed it Boolean type variables, but as soon as I try to use it with symbolic registers it goes really slow. (e.g. can be used for adding up to two symbolic registers <16bit word).

I found that by using BooleanMinimize function at each computation of the sum & carry bit this will simplify the terms when Boolean type bits are shuffled in.

I am new to Mathematica and was wondering if there are better ways of performing the task (better use of Mathematica built in functions, parallelization possibilities if for example carry look ahead is used instead, or maybe I am asking too much and by nature of the problem this will bog down as multiple symbols/ operations are propagated to the next bit).

Thank you, any information is well received.


Edit1, reply to @Mr. Henrik Schumacher asking for example of inputs/ outputs (I forgot) :

Example with Boolean Type only inputs (LSB at the top): enter image description here

Example with Symbolic/Boolean Type inputs (LSB at the top, performed only on 4bits for display reasons): enter image description here

Example with Symbolic Type only inputs (LSB at the top, performed only on 4bits for display reasons, operation can be performed on 16ish bits symbolic registers, having more kills my PC and this what I want to fix): enter image description here


Edit2: test code added

In[501]:= bits = 8;
regSym1 = Table[Subscript[b, 1, i], {i, 1, bits}];
regSym2 = Table[Subscript[b, 2, i], {i, 1, bits}];
regSym3 = rippleAdd[regSym1, regSym2, False];
{MatrixForm[regSym1], MatrixForm[regSym2], Simplify[MatrixForm[regSym3]]}

Out[505]= Out[505]
$\endgroup$
8
  • $\begingroup$ Some example input and expected output would be nice. $\endgroup$ – Henrik Schumacher Apr 4 at 13:38
  • $\begingroup$ I've done something like this before for 8-bits: see here pastebin.com/jqVu774J Why do you need to write this program? If you're doing SAT solving / concolic execution / taint analysis things, then you're better off using the z3 library (python/c++) where there are BitVec types. $\endgroup$ – flinty Apr 4 at 15:05
  • $\begingroup$ @HenrikSchumacher please see edit 1, thanks. $\endgroup$ – Bogdan Sofalca Apr 4 at 16:12
  • 1
    $\begingroup$ Please add a complete example in copy-pastable format. I cannot tell what exactly are the input forms here. $\endgroup$ – Daniel Lichtblau Apr 4 at 16:40
  • 1
    $\begingroup$ @BogdanSofalca - it looks like minimizing a 32-bit add in Mathematica is impractical, but again I think it could help find a better answer if you told us why you need to solve this problem in the first place, as there may be alternatives there. $\endgroup$ – flinty Apr 4 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.