Index
> Projects and Ideas > BigIntegers in fasm |
| Author |
|
|
Madis731 05 Oct 2006, 12:28
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 05 Oct 2006, 12:46
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 05 Oct 2006, 12:50
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 |
|
|
Madis731 05 Oct 2006, 12:53
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 05 Oct 2006, 13:03
|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 05 Oct 2006, 13:22
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 05 Oct 2006, 13:23
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 05 Oct 2006, 13:25
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 05 Oct 2006, 16:57
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 05 Oct 2006, 19:45
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 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 05 Oct 2006, 20:07
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 06 Oct 2006, 14:22
you're welcome
 |
|||
|
06 Oct 2006, 14:22 |
|
|
Madis731 06 Oct 2006, 17:15
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 11 Oct 2006, 12:40
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 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 23 Oct 2007, 04:00
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:
|