flat assembler
Message board for the users of flat assembler.
Index
> Main > Working with big numbers Goto page Previous 1, 2 
Author 

bitRAKE
I'd like to suggest working in a residual number system (RNS) because it is very parrallel in nature. It is costly to transfer between number systems, but often that only needs to be done at beginning and end of problem. Which means it is not a solution at the single operation level.
http://www.math.utah.edu/~pa/MDS/residual.html ...and it is easy to understand/implement at the code/instruction level. 

08 Jan 2008, 05:36 

MCD
@vid: your algorithm is just a nice and clean rearangement of the usual multiplication algorithm. But in case most of your factors are only a few times bigger than the word size of 32..64bit(maybe say up to 256..4096bits), your algorithm will suretainly outperform the others.
I can't say much more about this subject right now because I'm not into it, but if someone is interested in it, I found this interesting paper about a FFTbased big number multiply: http://citeseer.ist.psu.edu/yap00quickmul.html 

08 Jan 2008, 05:41 

Madis731
I dug into FFT a while ago when I wanted to perform A*B and A^B (powers not xor ) with big numbers. http://board.flatassembler.net/topic.php?t=4882 There are code samples about the primitive method, but they are not very good. I couldn't get the hang of FFT so I didn't convert it to using it.


08 Jan 2008, 08:40 

ATV
I have written multiply algorithms same way as you calculate with pen and paper. First code was written 198586 with 8bit 6502 assembly.
Later I have realize, that algorithm is very slow, better use already written librarys. Like GMP or something. They are over 10x faster. _________________ 6213186413*2^605+1 divides Fermat F(600) and 121531*2^30260+1 divides Fermat F(30256) 

08 Jan 2008, 15:14 

tom tobias
Madis731 wrote: ...I couldn't get the hang of FFT so I didn't convert it to using it. Any time varying signal can be expressed as a sum of a series of sinusoids. http://www.relisoft.com/Science/Physics/sound.html http://www.dspguru.com/info/faqs/fftfaq2.htm http://www.gweep.net/~shifty/portfolio/fftmulspreadsheet/index.html http://www.dataq.com/applicat/articles/an11.htm http://ccrma.stanford.edu/~lantz/fourier.html http://www.eeglossary.com/fft.htm 

08 Jan 2008, 21:17 

MCD
The concept around the (fast) Fourier transformation and even the discret cosinus transformation are quiet clear for me, but the thing I don't understand is how to use the FFT for things that are no functions.
Usually you apply the FFT to a function like for example f: t > E (t being time and E being energy) to get a FFTfunction of it: f_FFT: t > E, this is what tom tobias basically said Quote:
You can generalize this to any kind of function f: x > y where x and y are any kind of value. (This is a 1dimensional FFT, and of course FFTs can be any higher dimensions.) now, if you don't have those 2 values, but just 1 value, like it is the case for one big number, how do you make a FFT out of that? for me there is some value missing. (The DCT is a special case of the FFT, where the function is discretized and thus the integrals become sums. Also the evaluation points of the function are even spaced and their number is a power of 2 for 1 period). 

09 Jan 2008, 05:34 

bitRAKE
Imagine the number is a time variant signal  each bit is in fact multiple particles moving through the circuitry! Either way (parallel or serial) we look at it the bits don't arrive at the same time.


09 Jan 2008, 08:25 

Picnic
vid wrote: hi, i wrote an article how to do basic operations with bignums (big numbers, more than 32 / 64 bits): Interesting and instructive article vid. 

22 Nov 2008, 21:45 

Picnic
Hi guys, sorry if my question sounds silly..
I have a big integer decimal string, how to know how many dwords i need to store this number in memory to binary value. Dividing the length of string by 10? 

10 Apr 2009, 19:58 

LocoDelAssembly
Good observation thimis, 2^32 is 10 digits long so 1 dword, then 2^64 is 20 digits long so 2 dwords, that immediately convinced me but unfortunately I found that 2^128 is 39 digits long... Rounding up would solve the problem but will round up always work? 2^256 is 78 digits long, 2^512 is 155 digits long... 2^65536 is 19768 digits long, here the error is severe, dividing by four gives only 1976.8 dwords but 2048 are needed.
Don't know how to precalculate the space needed but seems it is not that easy 

10 Apr 2009, 20:45 

jack2
NumberOfBits * Log10(2) = NumberOfDecimalDigits, for your examples you need add 1.
btw, 2^65536 is only 19729 digits 

10 Apr 2009, 23:31 

Picnic
That was a very helpful tip, there was a magic number after all
jack2 & LocoDelAssembly thanks a lot guys. 

11 Apr 2009, 01:11 

LocoDelAssembly
jack2, it was so simple... Thanks for the tip. Now another problem though, up to which string length the calculation will not deviate from the real result? (using plain FPU)


11 Apr 2009, 01:39 

bitRAKE
FLDLG2 is one of the FPU constants.
(Will be accurate to 2^64 bits I presume.) Code: ; TOS is number of bits fldlg2 fmul frndint ; needs round mode 10b (ceiling) ; TOS is number of decimal digits 

11 Apr 2009, 04:01 

Picnic
vid, sorry for any offtopic
bitRAKE wrote: needs round mode 10b (ceiling) Is this how to set round mode 10b?. I'm an FPU beginner. Code: .data cw rw 1 .code ; fstcw [cw] fwait mov ax, [cw] or ax, 0800h mov [cw], ax fldcw [cw] ; 

24 May 2009, 19:53 

bitRAKE
That looks good unless the round mode starts as 01b or 11b. An instruction which clears the first bit of the round mode is needed. FWAIT hasn't been needed since 386/486 days, iirc.
Code: fnstcw [cw] and [cw],not 1100'0000'0000b ; clear round mode or [cw], 1000'0000'0000b ; set ceiling round mode fldcw [cw] fnstcw [cw] and [cw],not 11'0000'0000b ; clear precision mode or [cw], 11'0000'0000b ; set double extended precision fldcw [cw] Raymond Filiatreault's tutorial should get you up to speed fairly quickly, imho. 

24 May 2009, 22:33 

Goto page Previous 1, 2 < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.