Hi there,

i'm not sure if this topic was discussed before ?
Could somebody please, give me a hint about
how to release the basic calcuations in 128bit
using only 32 bit.

Ok ADD would be with carry as is SUB but
i cannot get the solution for MUL signed and unsigned.
divide is horror :confused:

Logic instructions would be analogous to the 32 bit,
right?, ok how about NEGATE.

I'm enclosed in a 32bit universe.
Posted on 2001-11-12 13:09:59 by marsface
The sane thing would be finding a bignum library. Miracl, freelip,
or GNU MP.
Posted on 2001-11-12 14:36:42 by f0dder
I agree f0dder.

Maybe you know the abyss BigInteger Java classes,
you just add,add,add,add, multiply, add, and there
is no end. :grin:
Posted on 2001-11-12 14:55:57 by marsface
Remember elementary school? :) It's like this:
;     ABCD      ABC      AB

; x EFGH x DEF x CD
; -------- ------- ------
; DH FC BD
; DGo FBo ADo
; CHo ECo BCo
; DFoo FAoo + ACoo
; CGoo EBoo ------
; BHoo DCoo ACBD
; DEooo EAooo AD
; CFooo DBooo BC
; BGooo +DAoooo ------
; AHooo -------
; CEoooo DAFAFC
; BFoooo EB
; AGoooo DC
; BEooooo
; AFooooo EAFB
;+AEoooooo DBEC
;--------- -------
See the pattern? Each letter is a DWORD.
Posted on 2001-11-12 16:14:27 by bitRAKE
I like the explanation, bitRake,this helps me.
:)
Posted on 2001-11-13 15:15:09 by marsface
No problem, it's straight out of my source code. ;)
You wanted a hint. My code isn't exactly finished, but it
is made to multiply two values of any size.
Posted on 2001-11-13 22:03:45 by bitRAKE
Does your code have division ??
Which way does look the pattern ??
Posted on 2001-11-14 12:56:31 by marsface
division can be done by first left-aligning the divisor to the dividend and then subsequently subtracting the divisor and shifting it to the right. i wrote some code to calculate remainders that way ;)
Posted on 2001-11-14 13:37:09 by Tola
Nonbinary division looks like this (example is decimal):


428 ) 123456
0 000
---
0 1234
3 1284 estimated quotient (12 / 4)
----
-50 too much
428 add back some
---
2 3785 corrected quotient digit
8 3424
----
8 3616
8 3424
----
8 192

divide 123456 by 428
quotient = 288, remainder = 192
Knuth's Art of Computer Programming, Vol. 2: Seminumerical Algorithms may have some interesting shortcuts.
Posted on 2001-11-14 14:29:26 by tank
I haven't got to division, yet. The multiply algorithm recursively transverses both numbers from the least dwords. I don't think it's optimal, but the algorithm is pretty to me - small code that does much. ;) It does the least number of multiplies, but some extra adds are used because only one destination buffer is used. I should finish it so I can post it here.

The technique is divide and conquer: the dword arrays are divided (split) in half until one of them is a single dword. Then the multiply takes place, and the previous unmultiplied segments are loaded. Sounds confusing, but it isn't.
Posted on 2001-11-14 17:46:55 by bitRAKE
When I did this in *gag* c++ (so sue me :grin: ) for a bigInt class i just simulated mult & div by going to binary that way you only have to compare then add/sub & shift. No mult or div instructions needed. Works exactly like your paper & pencil method just in binary. Fair warning tho it's likely not to be the fastest or best solution... I was look for a workaround at the time.
Posted on 2001-11-14 18:44:14 by rafe
It's best to make use of the MUL if you can. Imagine 2 numbers that are over a million digits each multiplied together. My algorithm would finish in my lifetime. ;) And the data for all the numbers (both sources and destination) would only occupy < 4 megs.

marsface, in binary NEG = NOT + 1 :alright:
Posted on 2001-11-14 21:56:04 by bitRAKE
I'm not going to defend the method I used to the death or anything there are faster methods. grrr... but don't imply my algorithms are exponential :grin: It's amazing how that implication can get a coder riled.

I'll code it if I have to prove it but the method I outlined had a big-O that is linear to the number of bits in the larger int. Average case it's time will be sub-linear. Space reqirements? I used 3 oper notation so it's only the result value plus an intermediate accum sometimes... roughly 6x the largest int total, including arguments.

Also, for simplicity sake (yes bitRake it slows things down slightly) I used a sign flag but I didn't use twos- or ones-complement. So the neg wound up being a bit toggle in the struc. You have to check for +/- zero & you'll lose a number off the range of the low end... oh well. You may also consider flagging +/- inf and other things too. I actually flagged zero too.
Posted on 2001-11-15 14:15:05 by rafe
Thanks for contribution fellows! :alright:

bitRake as i read this : NEG = NOT + 1
i spoke to me : why thinking simple when i it goes complex too.

Is it better then to check the numbers first, if are negative/positive. Set flag accordingly, then make both
positive. (simply by clearing the MSB)
Perform a unsigned multiply/division and finally set the sign ???
Posted on 2001-11-15 15:29:24 by marsface
rafe, sorry I didn't mean to imply exponential algorithm. Just my hyperbole. ;) I'm planning on using flags for many things: sign, irrational numbers, infinity, etc. Maybe, zero too - thanks for the idea. If I could figure out the signed multiply, I'd be using MMX, but it escapes me now.

marsface, I wouldn't do a multi-precision NEG, but if you needed to - then that is how it's done. :rolleyes:
Posted on 2001-11-15 15:54:00 by bitRAKE