flat assembler
Message board for the users of flat assembler.

Index > Main > Working with big numbers

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
N(N+1)/2= 0.5 N^2 + 0.5 N, which is just O(N^2)
For O() notation it doesn't matter whether it is 10*N^2 or 0.0001*N^2, it's stil O(N^2)

Why? Because for sizes large enough A*N^2 will always be larger than B*N and smaller than C*N^3, no matter what A, B and C are.
Post 07 Jan 2008, 15:02
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2942
Location: vpcmipstrm
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.
Post 08 Jan 2008, 05:36
View user's profile Send private message Visit poster's website Reply with quote
MCD



Joined: 21 Aug 2004
Posts: 604
Location: Germany
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 FFT-based big number multiply:
http://citeseer.ist.psu.edu/yap00quickmul.html
Post 08 Jan 2008, 05:41
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
I dug into FFT a while ago when I wanted to perform A*B and A^B (powers not xor Razz) 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.
Post 08 Jan 2008, 08:40
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
I have written multiply algorithms same way as you calculate with pen and paper. First code was written 1985-86 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)
Post 08 Jan 2008, 15:14
View user's profile Send private message Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
Madis731 wrote:
...I couldn't get the hang of FFT so I didn't convert it to using it.
I believe that most of us have trouble comprehending it!!! I know I do. It may be just sukoshi easier to understand, if one begins instead with the DFT (discrete Fourier transform), because the FFT is fast, only because of eliminating the many redundant multiplications found in the traditional DFT. The fastest FFT uses a "split radix", i.e. Radix 2 mixed with radix 4. Again, this is not necessary to study, in order to make (a little) progress on the DFT itself. The main point of Fourier's brilliant discovery is this:
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
Post 08 Jan 2008, 21:17
View user's profile Send private message Reply with quote
MCD



Joined: 21 Aug 2004
Posts: 604
Location: Germany
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 FFT-function of it: f_FFT: t -> E, this is what tom tobias basically said
Quote:

The main point of Fourier's brilliant discovery is this:
Any time varying signal can be expressed as a sum of a series of sinusoids.

You can generalize this to any kind of function f: x -> y where x and y are any kind of value. (This is a 1-dimensional 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).
Post 09 Jan 2008, 05:34
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2942
Location: vpcmipstrm
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.
Post 09 Jan 2008, 08:25
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
Picnic
vid wrote:
hi, i wrote an article how to do basic operations with bignums (big numbers, more than 32 / 64 bits):

http://www.x86asm.net/articles/working-with-big-numbers-using-x86-instructions/

Interesting and instructive article vid.
Post 22 Nov 2008, 21:45
View user's profile Send private message Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
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?
Post 10 Apr 2009, 19:58
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
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 Sad
Post 10 Apr 2009, 20:45
View user's profile Send private message Reply with quote
jack2



Joined: 06 Jul 2008
Posts: 31
jack2
NumberOfBits * Log10(2) = NumberOfDecimalDigits, for your examples you need add 1.
btw, 2^65536 is only 19729 digits
Post 10 Apr 2009, 23:31
View user's profile Send private message Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
Picnic
That was a very helpful tip, there was a magic number after all Smile
jack2 & LocoDelAssembly thanks a lot guys.
Post 11 Apr 2009, 01:11
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
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)
Post 11 Apr 2009, 01:39
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2942
Location: vpcmipstrm
bitRAKE
FLDLG2 is one of the FPU constants. Very Happy
(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    
Post 11 Apr 2009, 04:01
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
Picnic
vid, sorry for any off-topic
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]
        ;
    
Post 24 May 2009, 19:53
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2942
Location: vpcmipstrm
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]    
It's customary to preserve the control word and restore it at the end of the program (or long calculation) - with regard to speed: don't want to be changing it for only a couple instructions.

Idea Raymond Filiatreault's tutorial should get you up to speed fairly quickly, imho.
Post 24 May 2009, 22:33
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.