wood burning stoves 2.0*
The moose likes Java in General and the fly likes First 10 digits of the sum of 100 50 digit numbers (Project Euler # 13) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "First 10 digits of the sum of 100 50 digit numbers (Project Euler # 13)" Watch "First 10 digits of the sum of 100 50 digit numbers (Project Euler # 13)" New topic
Author

First 10 digits of the sum of 100 50 digit numbers (Project Euler # 13)

Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

Ok, I stored the numbers in a String array and I'm trying to parse them one at a time and store them into a long variable. Is 50 digits too large for a long data type?? If so should I be using BigInteger or some other data type in java???

Here's what I have so far:
Whenever I run this code, It throws a NumberFormatException every iteration.



Thanks,
Hunter M.


"If the facts don't fit the theory, get new facts" --Albert Einstein
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19651
    
  18

Hunter McMillen wrote:Is 50 digits too large for a long data type?? If so should I be using BigInteger or some other data type in java???

Yes to both questions. A long can only hold up to 2^63-1, which is 9,223,372,036,854,775,807. For anything larger, you will have to use float / double (but you'll precision) or BigInteger.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
This one becomes pretty trivial since the standard Java library has an arbitrary precision integer class (BigInteger). For (hypothetical) extra credit, how would you roll your own BigInt class (with an add() method)?


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

Ok so here's what I have with the BigInteger changes, Sorry Garret I'm not really sure what you mean by making my own add() method for BigInteger.




This gave me the correct answer however by using the BigInteger's built in add() method.
Thanks for your help guys.

Hunter M.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
I was half joking that since Java has a BigInteger class in the standard library, this question is pretty trivial. What might you do in a language that only supported 32 bit ints or 64 bit longs but didn't already have a class designed for arbitrary length integers. I was calling the class that you might make BigInt:


How would you internally represent arbitrary precision integers? How would you implement the add() and parse() methods. This to me seems a more interesting question since the problem from Project Euler was relatively easy.
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

Those are interesting questions, unfortunately I have no idea. Im not sure I'm good enough yet to tackle that question.

Hunter.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
One representation suggested by the Wikipedia article would be to use an array of ints with each int representing a digit in base 1000.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37953
    
  22
Can you remember how you were taught to add when you were little in school? Add the units, carry 1 if over 9, then add the 10s. That is the basis for the add() method.
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

That's a pretty cool article, thanks for linking it Garret; I'm going to work on that over the next few weeks or so and ill post what I have by then.

Hunter.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11153
    
  16

Campbell Ritchie wrote:Can you remember how you were taught to add when you were little in school? Add the units, carry 1 if over 9, then add the 10s. That is the basis for the add() method.

I had to implement something like this once in my algorithms class. I basically wrote a linked list, putting each digit into a node. it was quite a pain, but I got it to work, and was pretty proud of it.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14074
    
  16

fred rosenberger wrote:I had to implement something like this once in my algorithms class. I basically wrote a linked list, putting each digit into a node. it was quite a pain, but I got it to work, and was pretty proud of it.

The idea is good, but this is ofcourse super-inefficient...

Note that the source code for BigInteger is available. Look in your JDK installation directory for the file src.zip, you can find BigInteger.java in there.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41089
    
  44
I've done a number of the Project Euler puzzles, but have always thought that using BigInteger was a bit like cheating. There's much more to be learnt by avoiding it, IMO. Maybe you can rewrite the code without using it when you're a bit farther down the road.


Ping & DNS - my free Android networking tools app
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: First 10 digits of the sum of 100 50 digit numbers (Project Euler # 13)
 
Similar Threads
Sum the digits of an integer.
Sum of Digits
Highest Number of Consecutive Primes
Scanner class help
why are the answers different?