[fasmg]Y multiply uses O(nlgn) ways while division in O(n^2)

Index > Main > [fasmg]Y multiply uses O(nlgn) ways while division in O(n^2)

Author

Thread

l4m2

Joined: 15 Jan 2015
Posts: 674

l4m2 02 Jan 2017, 01:41

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

02 Jan 2017, 01:41

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 02 Jan 2017, 12:56

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

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

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.

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 might not be very fast, but still reasonable.

02 Jan 2017, 13:14

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 02 Jan 2017, 13:35

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 might not be very fast, but still reasonable.

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.

02 Jan 2017, 13:35

l4m2

Joined: 15 Jan 2015
Posts: 674

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

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:	640 Time(s)

03 Jan 2017, 04:39

Tomasz Grysztar

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

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

Joined: 15 Jan 2015
Posts: 674

l4m2 03 Jan 2017, 09:29

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

03 Jan 2017, 09:29

Tomasz Grysztar

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

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.

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.

03 Jan 2017, 12:24

l4m2

Joined: 15 Jan 2015
Posts: 674

l4m2 03 Jan 2017, 12:42

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

03 Jan 2017, 12:42

< 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