flat assembler
Message board for the users of flat assembler.
Index
> Main > [fasmg]Y multiply uses O(nlgn) ways while division in O(n^2) 
Author 

l4m2 02 Jan 2017, 01:41
Code: x = 1 shl (1 shl 28) y = 1 shl (1 shl 28) z = x*y Code: x = 1 shl (1 shl 18) y = 1 shl (1 shl 17) z = x/y 

02 Jan 2017, 01:41 

Tomasz Grysztar 02 Jan 2017, 13:14
revolution wrote: I'm pretty sure that the multiply algorithm is O(n^2) also. It just has a smaller hidden C value. revolution wrote: Do you know of an O(n lg n) algorithm for precise integer division? 

02 Jan 2017, 13:14 

revolution 02 Jan 2017, 13:35
Tomasz Grysztar wrote:
Tomasz Grysztar wrote:


02 Jan 2017, 13:35 

l4m2 03 Jan 2017, 04:39
Code: D=9 B=pow(D, 10 000 000) ; 0.630680 s A=B*B ; 0.783547 s A=A/B ; 6.541880 s A=A+D ; 0.000001 s A=A*B ; 0.967101 s


03 Jan 2017, 04:39 

Tomasz Grysztar 03 Jan 2017, 07:04
For fast big integer calculations please check out HeavyThing. It is free and open source.


03 Jan 2017, 07:04 

l4m2 03 Jan 2017, 09:29
Tomasz Grysztar wrote: For fast big integer calculations please check out HeavyThing. It is free and open source. here x means the length of x. a+b=f: O(f) ab=f: O(a+b) a*b=f: O(flgf) or O(a b) a/b=f: O(alga) or O(a b) a^b=f: O(flgf) 

03 Jan 2017, 09:29 

Tomasz Grysztar 03 Jan 2017, 12:24
revolution wrote: Thanks for the link. They say "practical", but there are lots of places to accidentally introduce bugs into that. But still not the n lg n that l4m2 is intimating. l4m2 wrote: The algorithm is well known and have no too much diff. 

03 Jan 2017, 12:24 

l4m2 03 Jan 2017, 12:42
Quote: This should not really concern fasmg, 

03 Jan 2017, 12:42 

< Last Thread  Next Thread > 
Forum Rules:

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