flat assembler
Message board for the users of flat assembler.

Index > Projects and Ideas > BigIntegers in fasm

Author
Thread Post new topic Reply to topic
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
Post 05 Oct 2006, 12:14
View user's profile Send private message Reply with quote
Madis731



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

I need a fast big integerdivision for primenumber detection/verification

Very HappyVery HappyVery HappyVery Happy 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 Smile
codelab wrote:

and guess maybe a 16 or 32 bit base of the number woud be the fastest approach?
erm...how about 2

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 05 Oct 2006, 12:28
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
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;    
Laughing

I know I'm just exaggerating...
Post 05 Oct 2006, 12:46
View user's profile Send private message Reply with quote
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
Post 05 Oct 2006, 12:50
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
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 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...
Post 05 Oct 2006, 12:53
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
|http://www.effervescence.com/" is broken and "prv.pl" is Polish server, so you'd need sylwek, or tomasz, or anyone
Post 05 Oct 2006, 13:03
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
Oh Sad my bad - *.pl written all over - I don't know why I assumed *.sk
Gotta stop working today Very Happy
Post 05 Oct 2006, 13:22
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
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..
Smile
Post 05 Oct 2006, 13:23
View user's profile Send private message Reply with quote
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    
Post 05 Oct 2006, 13:25
View user's profile Send private message Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
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


Description:
Download
Filename: bigshit09.zip
Filesize: 11.06 KB
Downloaded: 490 Time(s)

Description:
Download
Filename: biglib.zip
Filesize: 20.94 KB
Downloaded: 488 Time(s)


_________________
[not enough memory]
Post 05 Oct 2006, 16:57
View user's profile Send private message Reply with quote
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
     add esi,4
     loop divloop

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

.end start        

.)
Post 05 Oct 2006, 19:45
View user's profile Send private message Reply with quote
codelab



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

check attachment

Excellent, thats exactly what I was looking for, going to be fun to speed test this !
number crunching ahead!!
Post 05 Oct 2006, 20:07
View user's profile Send private message Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
you're welcome Wink
Post 06 Oct 2006, 14:22
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
codelab: this is very easy to divide BIGNUM with machine word, but do vice versa Smile 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 ; Very Happy
    
Post 06 Oct 2006, 17:15
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
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 false-positives etc.. please explain!
Laughing 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 Laughing sorry for the confusion
Post 11 Oct 2006, 12:40
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
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    
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.
Post 23 Oct 2007, 04:00
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:  


< 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-2019, Tomasz Grysztar.

Powered by rwasa.