Math Help Forum

Math Help Forum Feed Site Feed

Go Back   Math Help Forum > University Math Help > Other Advanced Topics
Reply
 
Thread Tools Display Modes
  #1  
Old October 16th, 2008, 07:28 PM
Newbie
 
Join Date: Oct 2008
Posts: 2
Country:
Thanks: 0
Thanked 0 Times in 0 Posts
i_heart_pandas is on a distinguished road
Default perform basic operations on large numbers algorithm?

is there such an algorithm for doing something like add a large integral numbers in sections?

the reason i ask is in computer science numbers can't be bigger than 2^32, so to emulate operations of a number of 2^256 you have to calcuate it doing many smaller calculations.

now i know that to mulitply two large(positive) numbers you can put them in a box, say 153 * 86 can be represented as (100*80)+(100*6)+(50*80)+(50*6)+(3*80)+(3*6) which is the only idea i have to work this out

basically the result of a small calcuation can't result in a number −2,147,483,648 to +2,147,483,647 (-2^31 to 2^31)

so i guess all calcuations should be done with two numbers below 2^16 so that the outcome can't be greater than 2^32

any help would be apprecitated, this isn't homework or anything just trying to write something?

thanks for your time
Reply With Quote
Advertisement
 
  #2  
Old October 17th, 2008, 09:19 AM
Super Member

 
Join Date: Aug 2008
Location: Lyon, France
Posts: 735
Country:
Thanks: 44
Thanked 469 Times in 390 Posts
Laurent is a name known to allLaurent is a name known to allLaurent is a name known to allLaurent is a name known to allLaurent is a name known to allLaurent is a name known to all
Default

Quote:
Originally Posted by i_heart_pandas View Post
is there such an algorithm for doing something like add a large integral numbers in sections?
Yes, there is, and this is like how you learnt to add numbers at school: Begin from the right. Add the corresponding sections, this gives you a number that fits in a section plus a carry. Then add the carry to the next section (to the left) of any of the numbers you're adding. And do the same for the next section.
To do this, you must be sure that the sum of any two sections + a carry (hence 3 times the maximum number in a section) does not exceed the capacity of the type of variable you use.

For the multiplication, this is the same: like at school, to multiply a by b, first multiply a by the right-most section of b (you do this by multiplying section after section and adding the carries like before), then multiply a by the next section of b, and sum this with the previous result, and so on.
To do this, you must be sure that the product of any two sections + a carry is not too large (you can use another type of variable to store the product before you compute and substract the carry).

Multiplying numbers is a long task, that's why people tried to find faster algorithms. The most efficient one relies on FFT (fast fourier transform), it is much more efficient than the "school algorithm" but more complex to implement.

To take better advantage of the structure of computers, the "sections" are usually defined using the binary expression for a number, and the translation from/to digits (base 10) is done at the beginning/end, once and for all. But it is easier to define sections in base 10 if you want to write a sample program of addition/multiplication of large numbers.

There must be a lot of ressource on the internet about this, you should look for it.
Reply With Quote
  #3  
Old October 17th, 2008, 10:50 AM
Newbie
 
Join Date: Oct 2008
Posts: 2
Country:
Thanks: 0
Thanked 0 Times in 0 Posts
i_heart_pandas is on a distinguished road
Default

yes thanks, i've looked into these algorithms and found out that they where easier to find than i thought, thanks
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off
Forum Jump


All times are GMT -7. The time now is 11:15 PM.


Powered by vBulletin® Version 3.7.3
Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.2.0 ©2008, Crawlability, Inc.
©2005 - 2009 Math Help Forum


Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.