flat assembler
Message board for the users of flat assembler.

 Index > Projects and Ideas > BigIntegers in fasm
Author
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
Hi all (other) brains, does anybody else like the idea of big integers and some basic arithmetic on them ?
I need a fast big integerdivision for primenumber detection/verification
and guess maybe a 16 or 32 bit base of the number woud be the fastest approach?
sincerely, codelab
05 Oct 2006, 12:14

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
codelab wrote:
Hi all (other) brains, does anybody else like the idea of big integers and some basic arithmetic on them ?

Of course - try my try on powering http://enos.itcollege.ee/~mkalme/PowerMul.7z
I've got some more ideas that I haven't put into effect yet.
codelab wrote:

I need a fast big integerdivision for primenumber detection/verification

Impossible!!!
Ok, sorry, now seriously, integer division will always be slow and prime numbers can't be detected - they can only be found with O(nlogn) or something where n is the number. Actually I would like to redefine the log() because it isn't equal to what it actually is. Anyway - its just trial and error
codelab wrote:

and guess maybe a 16 or 32 bit base of the number woud be the fastest approach?

_________________
My updated idol http://www.agner.org/optimize/
05 Oct 2006, 12:28
Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania
Borsuc
I have always been wondering: what if it's possible to do it with a sneaky approach, like:
Code:
```// WARNING, this code doesn't work!!
t = (x-2)/(x^(x>>1));
x = x^(x*(t&x)-(~x + t/(x+1 - ((x&2)>>1))));

if(x > t || (t-x)^(x*t)) prime=true;    ```

I know I'm just exaggerating...
05 Oct 2006, 12:46
Vasilev Vjacheslav

Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
for big integers try to use biglib from roy|fleur or jopas bigsh*t, both is open-source and written in masm (not so hard to porting, eh?)

http://www.effervescence.com - biglib
http://jopas.prv.pl - bigsh*t
05 Oct 2006, 12:50

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
The_Grey_Beast: that is maybe what we are looking for, but how did you come to that and does it work at least on some % of numbers and does it give some false-positives etc.. please explain!

Vasilev Vjacheslav: What makes it espescially easy is that its in Slovakian. I think I knew Russian before reading it, but I think we need to ask help from vid/MazeGen...
05 Oct 2006, 12:53
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
|http://www.effervescence.com/" is broken and "prv.pl" is Polish server, so you'd need sylwek, or tomasz, or anyone
05 Oct 2006, 13:03

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Oh my bad - *.pl written all over - I don't know why I assumed *.sk
Gotta stop working today
05 Oct 2006, 13:22
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
Quote:

Of course - try my try on powering http://enos.itcollege.ee/~mkalme/PowerMul.7z
I've got some more ideas that I haven't put into effect yet.

very nice ! That can def. be used.

Now to verify a prime candidate i know it takes some patience, impossible its not at all, currently finding 14 digit primes, but need to break this limit.

base2 and base16 would be compatible, but the higher base the faster you can get the rest after division I considered the algoritm similar to division done by hand:

100: 9=
9 100 = 11
9
10
9
1 is the rest or 100 mod 9=1

if we did base 100 here the answer would require fewer steps..
05 Oct 2006, 13:23
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
sorry for the format grrr, here correct:
Code:
```
100: 9=
9   100 =  11
9
10
9
1 is the rest or 100 mod 9=1    ```
05 Oct 2006, 13:25
Vasilev Vjacheslav

Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
Vasilev Vjacheslav: What makes it espescially easy is that its in Slovakian. I think I knew Russian before reading it, but I think we need to ask help from vid/MazeGen...

check attachment

_________________
[not enough memory]
05 Oct 2006, 16:57
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
Hi all, following snippet is a biginteger mod int, very easy (not fully tested)
it does a "hand" division without substitution
Code:
```; calculates Bigint mod int using base 2^32, biginteger range is only limited by memory
; by codelab
include 'win32ax.inc'

divisor equ 9

.data
;     bigint      dd 128,0,0,0,0,1
;     bigintlen   dd 0
bigint      dd 10,1000       ;in this case   10*2^32+1000 = 42949673961
bigintlen   dd 0

string     db 50 dup(32),0

.code

start:

mov esi,bigint
mov ecx, ((bigintlen-bigint)/4)
mov edx,0
mov edi,divisor

divloop:
mov eax,dword [esi]
div edi
loop divloop

invoke    wsprintf, string, 'remainder %i', edx
invoke    MessageBox,NULL,string,'',MB_OK
invoke    ExitProcess,0

.end start        ```

.)
05 Oct 2006, 19:45
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
hi Vasilev, thx have u used this?
Quote:

check attachment

Excellent, thats exactly what I was looking for, going to be fun to speed test this !
05 Oct 2006, 20:07
Vasilev Vjacheslav

Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
you're welcome
06 Oct 2006, 14:22

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
codelab: this is very easy to divide BIGNUM with machine word, but do vice versa ok, simply put the next one is a lot harder to come to:
Code:
```mov eax,dividable1
mov edx,dividable2
mov ecx,divisor1
mov ebx,divisor2
call do_the_division ;
```
06 Oct 2006, 17:15
Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania
Borsuc
The_Grey_Beast: that is maybe what we are looking for, but how did you come to that and does it work at least on some % of numbers and does it give some false-positives etc.. please explain!
The code is false, only a joke... I just wanted to say "something like that". I wrote it as I replied, didn't thought one minute sorry for the confusion
11 Oct 2006, 12:40
bitRAKE

Joined: 21 Jul 2003
Posts: 3455
Location: vpcmipstrm
bitRAKE
The mpn directory of GMP has many algorithms in AT&T syntax. That would be a good start for a FASM library. I have some algorithms which are specifically optimized for Athlon K7, but no big division.

Also, have some different types of prime sieves - one in SSE2 that is really fast at excluding small prime multiples for consecutive arbitrary size integers. It works great to filter numbers in a range before sending them on to more time consuming methods.

Factoring with division is not an option - just forget division even exists.

Code:
```Factor:
invoke Sqrt, [esp][4] ; num
;(should combine Sqrt algoritm to optimize further)
xor edx, edx
test eax, 1
sete dl
sub eax, edx

mov ecx, eax
mul eax
lea edx, [ecx*2]
mov ecx, [esp][4]
sub ecx, eax
mov eax, edx

_0:     cmp ecx, eax
jnc _1
sub eax, 4
sub ecx, eax
jne _0

shr eax, 1
shr edx, 1
retn 4    ```
This is an improvement on Fermat Factoring and faster than trail division when the factors get close. Have to use it recursively on odd numbers.

Number Theory will continue to be a hobby for me, and I'll do what I can to collect and create algorithms tuned to x86.
23 Oct 2007, 04:00
 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

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