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

revolution
I'm pretty sure that the multiply algorithm is O(n^2) also. It just has a smaller hidden C value.
Do you know of an O(n lg n) algorithm for precise integer division? 

02 Jan 2017, 12:56 

Tomasz Grysztar
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
Tomasz Grysztar wrote:
Tomasz Grysztar wrote:


02 Jan 2017, 13:35 

l4m2
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
For fast big integer calculations please check out HeavyThing. It is free and open source.


03 Jan 2017, 07:04 

l4m2
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 

l4m2
Quote: This should not really concern fasmg, 

03 Jan 2017, 12:42 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.