• Post Reply Bookmark Topic Watch Topic
  • New Topic

Project Euler Problem  RSS feed

 
Nathan Leniz
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

So I cleared that up but am having another problem. I'm using BigDecimal for exact precision, but after a million iterations checking values nothing is matching my test case. I'm currently processing Pythagorean Triplets and using the formula as long as m < n, then n2 - m2 = a, 2mn = b, and n2 + m2 = c.

Here's the snippet of code where I'm trying to do that, just want to make sure it's correct.


I'm using BigDecimal because I originally started with whole numbers but couldn't find anything that matched the test case, and since I'm looping through numbers almost a million times now and adding by .1 after each loop, I didn't think double would keep up very long in precision.
[ July 14, 2008: Message edited by: Nathan Leniz ]
 
Nathan Leniz
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, I finally found out what was happening and why it wasn't working. I won't go into details too greatly but for anyone else that isn't familiar with BigDecimal, just remember that 5 != 5.0 != 5.00
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What formula are you using for Pythagorean triplets? The whole idea of Project Euler puzzles is to get a nice simple algorithm.

You are looking for b^2 and (b+1)^2 and getting them to differ by a^2.
(b+1)^2 = b^2 + 2b + 1 so you are looking for a perfect square which is equal to 2b+1.
So you look for perfect squares which obviously have to be odd numbers and halve them.
1^2 = 1 = 2*0 + 1, so b = 0.
3^2 = 9 = 2*4 + 1, so b = 4.
5^2 = 25 = 2*12+1, so b = 12.

etc etc.

You don't need BigDecimal, only Big Integer. In fact to find the n-th Pythagorean triplet is now very easy . . .
No need for loops or anything.
You can find the 1000000th Pythagorean Triplet with longs and not need to bother with the java.math package classes.
 
Nathan Leniz
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was using
if m < n. then n2 - m2 = a, 2mn = b, and n2 + m2 = c

I'd appreciate a private message explaining your method if you don't mind. I'm slowly building up my own math library. Also, I haven't touched math in a LONG time, so I'm really rusty and find I'm googling almost everything.

Oh, and what I did was (I know it was probably the most horrible way to do it)
start with m = .1 and n = .2 then iterate through n by .1 a million times, after that increment m by .1 then do it again, a million times. All the while I was doing it I was being asked by the so "What are you doing" and my only reply was "using computing power".
[ July 15, 2008: Message edited by: Nathan Leniz ]
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Nathan Leniz:
[QBI'd appreciate a private message explaining your method if you don't mind. . .[/QB]
The policy is that everything is discussed on the forum, not by e-mail or private message. And I think I have told you quite enough;

The 837458th Pythagorean triplet is 1674915, 1402670128612, 1402670128613
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!