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

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: 20247
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: 8347
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: 20247
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: 588 Time(s)

03 Jan 2017, 04:39
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8347
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: 8347
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum