[Lua] Adding big numbers using strings

Dev Shed Forums Sponsor:

1200+ fellow developers rate and compare features of the top IDEs, like Visual Studio, Eclipse, RAD, Delphi and others, across 13 categories. Enjoy this FREE Download of the IDE User Satisfaction Study by Evans Data Corporation. Download Now!

October 9th, 2007, 07:02 PM

dustpyle_x3

Contributing User

Join Date: Nov 2006

Posts: 82

Time spent in forums: 2 Days 3 h 48 m 14 sec
Reputation Power: 4

[Lua] Adding big numbers using strings

I'm trying to figure out the first term in the Fibonacci sequence to have 1000 digits. Now, I know I could use some fancy big number library, but I like to do these problems without any libraries that aren't added automatically. For some reason, my sum() method is giving weird results. Here's my code:

Lua Code:

Original - Lua Code

-- What is the first term in the Fibonacci sequence to contain 1000 digits?                                                
                                                                                                                           
function sum (num1,num2) -- note to self: num2:len() >= num1:len() always                                                  
   local dif = num2:len() - num1:len() -- 0                                                                                
   local sum = ""                                                                                                          
   local carry = "0"                                                                                                       
   local cur = ""                                                                                                          
   for i=num1:len(),1,-1 do                                                                                                
      cur = num1:sub(i,i) + num2:sub(i+dif,i+dif) + carry .. "" -- 2                                                       
      sum = cur:sub(cur:len()) .. sum -- 2                                                                                 
      carry = (cur:sub(1,cur:len()-1) == "") and "0" or cur:sub(1,cur:len()-1) -- 0                                        
   end                                                                                                                     
   sum = ((num2.sub(1,dif) == "") and "0" or num2.sub(1,dif)) + carry .. sum -- 2                                          
   return sum                                                                                                              
end                                                                                                                        
                                                                                                                           
local f1 = "1"                                                                                                             
local f2 = "1"                                                                                                             
local term = 1                                                                                                             
while f1:len() < 1000 do                                                                                                   
   print(f2)                                                                                                               
   f1,f2 = f2,sum(f1,f2)                                                                                                   
   term = term + 1                                                                                                         
end                                                                                                                        
print(term)

-- What is the first term in the Fibonacci sequence to contain 1000 digits?                                                
                                                                                                                           
function sum (num1,num2) -- note to self: num2:len() >= num1:len() always                                                  
   local dif = num2:len() - num1:len() -- 0                                                                                
   local sum = ""                                                                                                          
   local carry = "0"                                                                                                       
   local cur = ""                                                                                                          
   for i=num1:len(),1,-1 do                                                                                                
      cur = num1:sub(i,i) + num2:sub(i+dif,i+dif) + carry .. "" -- 2                                                       
      sum = cur:sub(cur:len()) .. sum -- 2                                                                                 
      carry = (cur:sub(1,cur:len()-1) == "") and "0" or cur:sub(1,cur:len()-1) -- 0                                        
   end                                                                                                                     
   sum = ((num2.sub(1,dif) == "") and "0" or num2.sub(1,dif)) + carry .. sum -- 2                                          
   return sum                                                                                                              
end                                                                                                                        
                                                                                                                           
local f1 = "1"                                                                                                             
local f2 = "1"                                                                                                             
local term = 1                                                                                                             
while f1:len() < 1000 do                                                                                                   
   print(f2)                                                                                                               
   f1,f2 = f2,sum(f1,f2)                                                                                                   
   term = term + 1                                                                                                         
end                                                                                                                        
print(term)

You'll see that sum("1","1") is gives a result of "12", but I can't figure out why. Can anyone else see it?

October 10th, 2007, 12:00 AM

Lux Perpetua

Contributing User

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,418

Time spent in forums: 3 Weeks 4 Days 23 h 47 m 27 sec
Reputation Power: 334

Code:

num2.sub(1,dif)

Looks like a typo.

October 10th, 2007, 11:43 AM

dustpyle_x3

Contributing User

Join Date: Nov 2006

Posts: 82

Time spent in forums: 2 Days 3 h 48 m 14 sec
Reputation Power: 4

Oh whoops. Well now I have a few new problems:
1. All my numbers returned by sum have leading zeros. Easily fixed by changing return sum to return sum:gsub("0","")
2. Every time I run it, it dies on the 14 term of the sequence. It tells me I'm trying to perform arithmetic on a string value on line 9. Why would it randomly tell me this in the middle of the execution after that method has already been called multiple times?

Last edited by dustpyle_x3 : October 10th, 2007 at 11:47 AM.

October 10th, 2007, 08:13 PM

Lux Perpetua

Contributing User

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,418

Time spent in forums: 3 Weeks 4 Days 23 h 47 m 27 sec
Reputation Power: 334

Quote:

Originally Posted by dustpyle_x3

1. All my numbers returned by sum have leading zeros. Easily fixed by changing return sum to return sum:gsub("0","")

You should really think things through more carefully.

Quote:

Originally Posted by dupstyle_x3

2. Every time I run it, it dies on the 14 term of the sequence. It tells me I'm trying to perform arithmetic on a string value on line 9. Why would it randomly tell me this in the middle of the execution after that method has already been called multiple times?

You're telling me your program isn't giving you a useful message when it crashes. So make it. Have it print out the values of relevant variables at each step of the computation.

October 11th, 2007, 07:00 PM

dustpyle_x3

Contributing User

Join Date: Nov 2006

Posts: 82

Time spent in forums: 2 Days 3 h 48 m 14 sec
Reputation Power: 4

Ya, that was my next step after I couldn't find anything that would break it. Then it hit me that sum:gsub("0","") was replacing ALL the zeros. Changed that to tonumber(sum). Then it gave me some other error and I had to change num1,num2 = num2,sum(num1,num2) to num1,num2 = num2,sum(num1,num2).."" and now it's making it to like the 100th term, and then breaking. Same error as before too. Trying to perform arithmetic on a string on line 9. I'll see if I can't find what's wrong.

[edit] Oh wait, I see it. I'll be right back after I fix it.

Ok, complete. Final code:

Lua Code:

Original - Lua Code

-- What is the first term in the Fibonacci sequence to contain 1000 digits?                              
                                                                                                         
function sum (num1,num2) -- note to self: num2:len() >= num1:len() always                                
   local dif = num2:len() - num1:len()                                                                   
   local sum = ""                                                                                        
   local carry = "0"                                                                                     
   local cur = ""                                                                                        
   for i=num1:len(),1,-1 do                                                                              
      cur = num1:sub(i,i) + num2:sub(i+dif,i+dif) + carry .. ""                                          
      sum = cur:sub(cur:len()) .. sum                                                                    
      carry = (cur:sub(1,cur:len()-1) == "") and "0" or cur:sub(1,cur:len()-1)                           
   end                                                                                                   
   sum = ((num2:sub(1,dif) == "") and "0" or num2:sub(1,dif)) + carry .. sum                             
   return sum:gsub("^0+","")                                                                             
end                                                                                                      
                                                                                                         
local f1 = "1"                                                                                           
local f2 = "1"                                                                                           
local term = 1                                                                                           
while f1:len() < 1000 do                                                                                 
   f1,f2 = f2,sum(f1,f2)                                                                                 
   term = term + 1                                                                                       
end                                                                                                      
print(term)

-- What is the first term in the Fibonacci sequence to contain 1000 digits?                              
                                                                                                         
function sum (num1,num2) -- note to self: num2:len() >= num1:len() always                                
   local dif = num2:len() - num1:len()                                                                   
   local sum = ""                                                                                        
   local carry = "0"                                                                                     
   local cur = ""                                                                                        
   for i=num1:len(),1,-1 do                                                                              
      cur = num1:sub(i,i) + num2:sub(i+dif,i+dif) + carry .. ""                                          
      sum = cur:sub(cur:len()) .. sum                                                                    
      carry = (cur:sub(1,cur:len()-1) == "") and "0" or cur:sub(1,cur:len()-1)                           
   end                                                                                                   
   sum = ((num2:sub(1,dif) == "") and "0" or num2:sub(1,dif)) + carry .. sum                             
   return sum:gsub("^0+","")                                                                             
end                                                                                                      
                                                                                                         
local f1 = "1"                                                                                           
local f2 = "1"                                                                                           
local term = 1                                                                                           
while f1:len() < 1000 do                                                                                 
   f1,f2 = f2,sum(f1,f2)                                                                                 
   term = term + 1                                                                                       
end                                                                                                      
print(term)

And the answer is 4782

Thanks for your help!
[/edit]

Last edited by dustpyle_x3 : October 11th, 2007 at 07:11 PM.

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: