flat assembler
Message board for the users of flat assembler.

 Index > Main > Working with big numbers Goto page Previous  1, 2
Author
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland
Tomasz Grysztar 07 Jan 2008, 15:02
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.
07 Jan 2008, 15:02
bitRAKE

Joined: 21 Jul 2003
Posts: 4020
Location: vpcmpistri
bitRAKE 08 Jan 2008, 05:36
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

Joined: 21 Aug 2004
Posts: 602
Location: Germany
MCD 08 Jan 2008, 05:41
@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
08 Jan 2008, 05:41

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
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

Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV 08 Jan 2008, 15:14
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)
08 Jan 2008, 15:14
tom tobias

Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias 08 Jan 2008, 21:17
...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.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

Joined: 21 Aug 2004
Posts: 602
Location: Germany
MCD 09 Jan 2008, 05:34
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).
09 Jan 2008, 05:34
bitRAKE

Joined: 21 Jul 2003
Posts: 4020
Location: vpcmpistri
bitRAKE 09 Jan 2008, 08:25
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

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 22 Nov 2008, 21:45
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.

_________________
Hobby BASIC Interpreter
22 Nov 2008, 21:45
Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 10 Apr 2009, 19:58
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

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 10 Apr 2009, 20:45
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

Joined: 06 Jul 2008
Posts: 33
jack2 10 Apr 2009, 23:31
NumberOfBits * Log10(2) = NumberOfDecimalDigits, for your examples you need add 1.
btw, 2^65536 is only 19729 digits
10 Apr 2009, 23:31
Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 11 Apr 2009, 01:11
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

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 11 Apr 2009, 01:39
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

Joined: 21 Jul 2003
Posts: 4020
Location: vpcmpistri
bitRAKE 11 Apr 2009, 04:01
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

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 24 May 2009, 19:53
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]
;
```
24 May 2009, 19:53
bitRAKE

Joined: 21 Jul 2003
Posts: 4020
Location: vpcmpistri
bitRAKE 24 May 2009, 22:33
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.

Raymond Filiatreault's tutorial should get you up to speed fairly quickly, imho.
24 May 2009, 22:33
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum