flat assembler
Message board for the users of flat assembler.
Index
> Projects and Ideas > BigIntegers in fasm 
Author 

Madis731
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:
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:


05 Oct 2006, 12:28 

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 = (x2)/(x^(x>>1)); x = x^(x*(t&x)(~x + t/(x+1  ((x&2)>>1)))); if(x > t  (tx)^(x*t)) prime=true; I know I'm just exaggerating... 

05 Oct 2006, 12:46 

Vasilev Vjacheslav
for big integers try to use biglib from royfleur or jopas bigsh*t, both is opensource 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 

Madis731
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 falsepositives 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
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 

Madis731
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
Quote:
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
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
Madis731 wrote: 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
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, ((bigintlenbigint)/4) mov edx,0 mov edi,divisor divloop: mov eax,dword [esi] div edi add esi,4 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
hi Vasilev, thx have u used this?
Quote:
Excellent, thats exactly what I was looking for, going to be fun to speed test this ! number crunching ahead!! 

05 Oct 2006, 20:07 

Vasilev Vjacheslav
you're welcome


06 Oct 2006, 14:22 

Madis731
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
Madis731 wrote: 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 falsepositives etc.. please explain! 

11 Oct 2006, 12:40 

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 add ecx, edx _1: add edx, 4 sub ecx, eax jne _0 shr eax, 1 shr edx, 1 retn 4 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 

< Last Thread  Next Thread > 
Forum Rules:

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