mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-11-27, 20:20   #1
meknowsnothing
 
May 2007

3 Posts
Default Big integer speed in bases.

I'm curious on how the large integer arithmetic is usually implemented in programs. I know that the numbers are in the linked list. So for example if I want to multiply 123454452544545 by 543490553480954 then I have might have an element 545 in a list and 954 in another list. Then I multiply those numbers to get 519930, move 930 to the result list element and add carry.


I was thinking whether this is faster than transform those huge numbers to their binary representation, do multiplication in base 2 and transform the result to base 10. I know that in computers those numbers are already represented by bits but its representation depends on how the linked list has been built.

So, which is faster method to do the program that asks the user two big numbers in base 10 and outputs their product in base 10?
meknowsnothing is offline   Reply With Quote
Old 2008-11-27, 20:35   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×1,657 Posts
Default

Google and wikipedia are your friends.
Just read this - http://en.wikipedia.org/wiki/Multiplication_algorithm
The serious algorithms (like those for GIMPS) are outlined in the end
Batalov is offline   Reply With Quote
Old 2008-11-28, 03:30   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2·3·29·43 Posts
Default

Quote:
Originally Posted by meknowsnothing View Post
I'm curious on how the large integer arithmetic is usually implemented in programs. I know that the numbers are in the linked list. So for example if I want to multiply 123454452544545 by 543490553480954 then I have might have an element 545 in a list and 954 in another list. Then I multiply those numbers to get 519930, move 930 to the result list element and add carry.


I was thinking whether this is faster than transform those huge numbers to their binary representation, do multiplication in base 2 and transform the result to base 10. I know that in computers those numbers are already represented by bits but its representation depends on how the linked list has been built.

So, which is faster method to do the program that asks the user two big numbers in base 10 and outputs their product in base 10?
What you "know" is wrong. Linked lists would be grossly inefficient.

Run, don't walk, and get yourself a copy of The Art of Computer
Programming, Vol II. Read it. It will tell you everything you need
or want to know.

Multi-precision arithmetic is done internally using a radix that is a
power of 2, (the power depends mostly on the word size). Conversion
to base 10 happens very infrequently; almost always ONLY at input
or output time.
R.D. Silverman is offline   Reply With Quote
Old 2008-11-28, 03:32   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2·3·29·43 Posts
Default

Quote:
Originally Posted by Batalov View Post
Google and wikipedia are your friends.
Just read this - http://en.wikipedia.org/wiki/Multiplication_algorithm
The serious algorithms (like those for GIMPS) are outlined in the end
I don't trust Wikipaedia when it comes to technical details.
Such details are important in this application.

Read Knuth, Vol II.
R.D. Silverman is offline   Reply With Quote
Old 2008-12-01, 14:21   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×17×43 Posts
Default

If you find errors there feel free to correct them.
alpertron is offline   Reply With Quote
Old 2008-12-02, 00:44   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

25×367 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Multi-precision arithmetic is done internally using a radix that is a
power of 2, (the power depends mostly on the word size). Conversion
to base 10 happens very infrequently; almost always ONLY at input
or output time.
There's actually little or no advantage to using a power-of-2 base in a floating-based big-int implementation; one could very well use a power of 10 (or something else - the overall word size is more important than its factorization) in a generic multiprecision library based on floats. Powers of 2 are mainly handy for special moduli (Mersenne and Fermat) and for pure-integer work.
ewmayer is offline   Reply With Quote
Old 2008-12-02, 04:17   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Jeez I'm staying out of this debate
davieddy is offline   Reply With Quote
Old 2008-12-02, 12:41   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2×3×29×43 Posts
Default

Quote:
Originally Posted by ewmayer View Post
There's actually little or no advantage to using a power-of-2 base in a floating-based big-int implementation; one could very well use a power of 10 (or something else - the overall word size is more important than its factorization) in a generic multiprecision library based on floats. Powers of 2 are mainly handy for special moduli (Mersenne and Fermat) and for pure-integer work.
This is not quite correct. A power of 10 representation can not use all of
the bits in each word, even in floating point.

This results in requiring more limbs to represent each number. Run-time
depends on the number of limbs.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
pari-algorithm for finding Gaussian integer bases devarajkandadai Software 0 2017-10-05 04:54
pari-algorithm for finding Gaussian integer bases devarajkandadai Software 0 2017-07-11 05:42
k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
Other Bases? wblipp GPU Computing 50 2012-10-11 13:23
Starting new bases MrOzzy Conjectures 'R Us 104 2010-03-18 22:11

All times are UTC. The time now is 09:30.


Tue Oct 4 09:30:59 UTC 2022 up 47 days, 6:59, 0 users, load averages: 1.25, 1.05, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔