Showing off one of my chips cause idk where else i can show it and be proud

[skiller8641]

it works, it only does 8 bits by 8 bits and does a moultiplication in the end it will do 4 byte x 4 byte with a maximum output of 4 byte

[BenBE]

You just skipped the important part of the showing: How do the guts of it look like?

What algorithm/architecture do you use for the internal multiplier? Can this be "stacked"?

Are you for example using Karatsuba to divide and conquer?

[skiller8641]

a lot of bitshift, cables, adder, sweat and blood

[skiller8641]

but to do karatrsuba, doesnt one need multiplication from the beginning?

[BenBE]

No. The base case of Karatsuba in binary degenerates into addition and bit shifting.

https://en.wikipedia.org/wiki/Karatsuba_algorithm#Basic_step

With a 2x2 bit input AB * CD (m=1) you get:

z2 = AC
z1 = AD + BC
z0 = BD
and x*y = z2<<2m + z1<<m + z0

Rewriting z1 as:
z1 = (A+B)*(C+D) - z2 - z0

The multiply of z1 needs 2m bits, but for m=1 can be simplified to a simple lookup table:
Let i=A+B, and j=C+D, we observe: z3=i*j is 0 if i or j is 0, 1 if i and j is 1, 4 if i and j are 2, and 2 otherwise.
This gives for the result r2 = i1 && j1, r1 = i1 ^ j1, r0 = i0 && j0 (untested).

For larger steps, simply recurse with the step m-1 Karatsuba IC where-ever you need to multiply.

[skiller8641]

i got 10% of that so
here is list of question
z2 = AC here i take the first bit (highest?) from the first input and the second bit from the second input?
z2<<2m whats <<?
AB * CD (m=1) whats m?
The multiply of z1 needs 2m bits, 2mega? what do you mean it needs 2m bits

so for lets say 8bits numbers
not value but for easy of follow
01234567
abcdefgh
z1 = (0123+4567)*(abcd+efgh) - 0123abcd- 4567efgh
hmm i still dont get it

if i make a chip that takes in 2 2bit input
output is 1 4bit? defined by

The multiply of z1 needs 2m bits, but for m=1 can be simplified to a simple lookup table:
Let i=A+B, and j=C+D, we observe: z3=i*j is 0 if i or j is 0, 1 if i and j is 1, 4 if i and j are 2, and 2 otherwise.
This gives for the result r2 = i1 && j1, r1 = i1 ^ j1, r0 = i0 && j0 (untested).
?

[BenBE]

Take a look at the Wikipedia link I posted. The m is the number of bits of each factor. So if your number is e.g. 00101010, which is n=8 bit, you would split the number in halves of m=4 bit like A=0010 and B=1010. Similar for the second factor, e.g. 01000101 with C=0100 and D=0101.

You then proceed to calculate:

z2 = A * C = 0010 * 0100 = K4(0010, 0100) = 0000'1000
z0 = B * D = 1010 * 0101 = K4(1010, 0101) = 0011'0010
i = A + B = 0010 + 1010 = 1100
j = C + D = 0100 + 0101 = 1001
z3 = i * j = 1100 * 1001 = K4(1100, 1001) = 0110'1100

where K is the Karatsuba IC with 4 bit inputs and an 8 bit output. Construction is similar.

We then need to calculate

z1 = z3 - z2 - z0 = 0110'1100 - 0000'1000 - 0011'0010 = 0011'0010

And finally:

result = z2 << (2 * m) + z1 << m + z0 =
0000'1000 << 8 + 0011'0010 << 4 + 0011'0010 =
0000'1000'____'____ +
     0011'0010'____ +
          0011'0010 =
0000'1011'0101'0010

Now for the base case: If you only have two 2 bit numbers you get:

z2 = A * C = A && C
z0 = B * D = B && D
i = A + B (range 0..2)
j = C + D (range 0..2)
z3 = i * j

Where you can do a quick lookup table:

 * | 0 1 2
---+------
 0 | 0 0 0
 1 | 0 1 2
 2 | 0 2 4

From there you can build the logic equations for r0 (LSb), r1 (middle), ad r2 (MSb); observing the relations I mentioned above (i=i1<<1 + i0, j=j1<<1 + j0). Thus for the case of m=1 you can replace the whole multiplication trivially by an AND (z2, z0), and a lookup for z3. Combining the results can be done with normal addition/subtraction ICs.

I hope it gets more clear this way.

[skiller8641]

with a lot of fighting with chat gpt cause he gave me the karatsuba for a 2x2 containing a simple circuit for a 2x2
i have a 2x2 multiplier
i am now gonna try to make a 4x4 karatsuba cause if i understood right you can do a karatsuba for the mulplier you have squared