flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Main > [fasmg]Y multiply uses O(nlgn) ways while division in O(n^2)

Author
Thread Post new topic Reply to topic
l4m2



Joined: 15 Jan 2015
Posts: 570
[fasmg]Y multiply uses O(nlgn) ways while division in O(n^2)

Code:
x = 1 shl (1 shl 28)
y = 1 shl (1 shl 28)
z = x*y

it costs 13.2 s to compile

Code:
x = 1 shl (1 shl 18)
y = 1 shl (1 shl 17)
z = x/y

costs 12.2 s
Post 02 Jan 2017, 01:41
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14673
Location: Origae-6
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?
Post 02 Jan 2017, 12:56
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6310
Location: Kraków, Poland

revolution wrote:
I'm pretty sure that the multiply algorithm is O(n^2) also. It just has a smaller hidden C value.

It uses Karatsuba algorithm there, so it is O(n^~1.585).

revolution wrote:
Do you know of an O(n lg n) algorithm for precise integer division?

There is one with complexity similar to Karatsuba multiplication, but I wanted something simpler for fasmg core. I used the revised variant of the algorithm that fasm 1 uses, which I call "intemediate division" - since it is faster that slow division, but still quadratic.
Post 02 Jan 2017, 13:14
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14673
Location: Origae-6

Tomasz Grysztar wrote:

revolution wrote:
I'm pretty sure that the multiply algorithm is O(n^2) also. It just has a smaller hidden C value.

It uses Karatsuba algorithm there, so it is O(n^~1.585).

This is a good thing. I am pleased to be wrong about O(n^2).

Tomasz Grysztar wrote:


revolution wrote:
Do you know of an O(n lg n) algorithm for precise integer division?

There is one with complexity similar to Karatsuba multiplication, but I wanted something simpler for fasmg core. I used the revised variant of the algorithm that fasm 1 uses, which I call "intemediate division" - since it is faster that slow division, but still quadratic.

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.
Post 02 Jan 2017, 13:35
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 570
Some result on HugeCalc

Code:
D=9
B=pow(D10 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



Description: HugeCalc and HugeCalcU give using GUI. API is not free(it costs). The third calculation a开b次方 means the b-th root of a
Download
Filename: HugeCalc.zip
Filesize: 1.49 MB
Downloaded: 30 Time(s)

Post 03 Jan 2017, 04:39
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6310
Location: Kraków, Poland
Re: Some result on HugeCalc
For fast big integer calculations please check out HeavyThing. It is free and open source.
Post 03 Jan 2017, 07:04
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 570

Tomasz Grysztar wrote:
For fast big integer calculations please check out HeavyThing. It is free and open source.

The algorithm is well known and have no too much diff. The constant may vary because of the optimization.
here |x| means the length of x.
a+b=f: O(|f|)
a-b=f: O(|a|+|b|)
a*b=f: O(|f|lg|f|) or O(|a| |b|)
a/b=f: O(|a|lg|a|) or O(|a| |b|)
a^b=f: O(|f|lg|f|)
Post 03 Jan 2017, 09:29
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6310
Location: Kraków, Poland

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.

I did not finish my thought there. The paper shows that the complexity of integer division with remainder can be in fact reduced to the complexity of the multiplication algorithm you use. So you could theoretically use Fürer's multiplication there and obtain the same complexity for division (not practical, though).


l4m2 wrote:
The algorithm is well known and have no too much diff.

Good bignum libraries use many algorithms because the ones with lower complexity are only profitable for the large inputs. So it not unusual to use long multiplication for small inputs, switch to Karatsuba for slighly larger ones, for even larger ones use Toom-Cook and then Schönhage-Strasse for really huge numbers. This should not really concern fasmg, since operations on such large numbers are not really what this tool is for - just like its multi-pass resolving is not the right tool for solving equations, even though it occasionally is able to solve one. So the main aim was to keep it simple. Look at the size of bigint routines in HeavyThing library - they are almost as long as fasmg in its entirety, while are they are still a relatively simple ones.
Post 03 Jan 2017, 12:24
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 570

Quote:
This should not really concern fasmg,

The problem seems to be solved early --- the MUL is not nlgn but n^lb3. With a n^lb3 MUL a n^2 DIV is the guessable choice
Post 03 Jan 2017, 12:42
View user's profile Send private message 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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.