piles of cannonballs - Page 4

NickGlover · 2003-08-30, 00:11

Quote:

Originally Posted by tom11784

Also, the main programming thing at my school is C++, so anyone know how to get it to store a variable with more than 52 bits of precision (double-precision) since that seems to be around where the record currently lies.

long double gives you an 80-bit float (64 bits of precision). However, most of the math library functions are not implemented for long double's.

Also, there is unsigned long long which gives you a 64-bit unsigned integer on most systems.

These two types are the best you can do without writing your own big number classes or using pre-existing ones (like GMP).

Maybeso · 2003-08-30, 01:59

My version of Borland Pascal has a signed 64 bit float with fixed precision of 0 digits. ;) [edit] better description [/edit]
Basically a signed 64 bit int with auto-rounding (which can be a pain).

That was my main motivation for trying to build the middle pile from the base of the big pile. -- I can search to almost n = 2^31 for the big pile, with a max of n = 2^21 on the middle pile instead of on the sum.

After I get my first overflow error, I'll put checks in. It should let me search n = 2^31 to 2^63 to an ever-decreasing depth. By dividing by 2 & 3 first, I can get really close.

The pile sizes for n > 2meg found so far:[list]2132122 = 2130224 + 295722
2140708 = 1969230 + 1295380
2192458 = 2192428 + 75630
2207645 = 1911717 + 1556746
2209055 = 2203448 + 434230
2212429 = 1985945 + 1441763
2212748 = 2078068 + 1229878
2225894 = 2158023 + 992738
2240860 = 1930654 + 1594775[/list:u]The last line -->
1875398240518859420 = 1199396485472305120 + 676001755046554300
In that range, it checks 2.33 sizes per second.

If c00ler includes the time it takes to build his array in his timings, It might tip the balance in favor the other methods, especially at n > 1.5 meg.

I,ve tweaked my search to skip over bad sums. I tried these:

1. A silly pseudo square/cube-root with feedback - in an attempt to make an increasing sequence of tetrahedrals match my converging sum of triangles. The scary thing is it seems to work, but it uses 4 divides -- I wasn't sure how it compared.

2. A binary hop, which skips big gaps well, but with at least 4 compares per "row" or several conditionals.

3. Check mod 5, 10, or 20 and skip mismatches - mod 20 repeats, allowing a look-up table.
This worked great (and works for your nested for-next method), but my pascal has very slow multi-dim array access. A pointer implementation may be the fastest.

It turns out the fastest method was a binary hop on the first gap, and my silly hop on the remainder. (I tuned my hop to beat a binary search for either small gaps or big gaps, not both. still working on it.)

I thought of another bounds optimization while writing this post, now if only I can remember it when I'm done. . .

tom11784 · 2003-08-30, 07:01

Quote:

Originally Posted by c00ler

I used very stupid Delphi program and record is
6590687693369780+952833181691720=7543520875061500 balls
(sides are 340690,178808 and 356375 balls)
Who can beat it?

P.S. And who can prove that it has infinetely many solutions?

Where did you find this program and is the source code open for editting?

tom11784 · 2003-08-30, 08:46

After writing an 11-line program it took less than 15 seconds to produce the following list:

[code:1] 3 3 4 8 14 15 20 54 55 30 55 58
39 70 74 84 90 110 61 102 109 34 118 119
48 138 140 119 154 175 187 201 245 100 290 294
327 335 418 362 415 492 252 424 452 149 429 435
424 448 550 248 450 474 434 495 588 219 515 528
314 527 562 136 532 535 399 588 644 532 643 747
324 663 688 272 688 702 304 695 714 424 705 753
349 713 740 608 754 868 378 790 818 489 869 918
230 903 908 775 950 1098 968 1001 1241 878 1044 1220
703 1064 1158 922 1286 1428 855 1343 1450 290 1430 1434
367 1436 1444 1351 1478 1796 897 1621 1708 504 1629 1645
750 1690 1738 798 1818 1868 1609 1941 2256 1146 2072 2183
1139 2115 2220 438 2164 2170 1105 2303 2385 853 2417 2452
[/code:1]

Can anyone refresh my memory on how to get Ubasic to print to a file instead of the screen?

c00ler · 2003-08-30, 18:08

My new(just added some optimizations) program:
[code:1]
const rdd:extended =1/6;
rd:extended =1/3;
rd2:extended =1/9;
rd3:extended =4/9;
rdln3:extended =0.36620409622270323; //ln(3)/3
rdln1_5:extended=0.13515503603605479; //ln(1.5)/3
nn=4; //minimal N to be checked, >=4
nm=10000; //maximum N to be checked; 10M+ works fine (if you have enough RAM)
ndn=10; //delay(in Ns) between outputs of current N
var a:array of extended;
ai,u,v,x,y:extended;
t,r,i,j,n,i1:integer;
begin
setlength(a,nm+1);

for n:=1 to nm do
begin
x:=n+1;
a[n]:=(sqr(x)*(x)-(x))*rdd;
end;

for i:=nn to nm do
begin

if i mod ndn =0 then
begin
//output current N
end;

ai:=a[i];
u:=ai+sqrt(sqr(ai)-rd3);
v:=exp(rd*ln(u)+rdln1_5);
t:=trunc(v);
i1:=i-1;

for j:=t to i1 do
begin

y:=ai-a[j];
u:=y+sqrt(sqr(y)-rd2);
v:=exp(rd*ln(u)+rdln3);
r:=trunc(v);

if a[r]=y then
begin
// output i->j+r (sizes) and/or a[i]=a[j]+a[r] (numbers of balls)
end;

end;
end;
end;
[/code:1]

Quote:

Originally Posted by Maybeso

If c00ler includes the time it takes to build his array in his timings, It might tip the balance in favor the other methods, especially at n > 1.5 meg.

I don't need to rebuild it to test another n. To build it for n<=11megs my program needs 4-5 seconds. So it's about 4.5/11000000 sec more time needed for each n.

Now I'm checking n>10 megs faster than one per second. Soon I'll find and post 10M+ solution.

WANTED LIST:
1) n->a+b (let's use "->" for sizes of piles and "=" for numbers of balls) where a>=b and (n and a are prime),
2) n->a+b where n,a,b are all prime.
3) n->a1+b1 & n->a2+b2 , a1<>a2
4) n->a+b and n>1000 meg

Maybeso · 2003-09-03, 20:02

Hey C00ler,

Very Impressive!

I ported your code with no trouble to BP, and it really screams.
There is no way the other methods can compete in any range of significant size.

:

With just a small *rolling array, I had it spit out some of the variables/ratios for certain conditions.
*see third item. Here are several improvements to try.

I've never seen two solutions for a single n value. So I exit the inner loop after a solution is found.

I printed out t/n and j/n for valid solutions. t/n seems to converge to 0.788xx, and I never saw j/n < 0.801. Any t value that works for n = 4 should be small enough.[code:1]const
rdt_n : extended = 0.789; // limit of t/n.
...
// ai:=a[i];
// u:=ai+sqrt(sqr(ai)-rd3);
// v:=exp(rd*ln(u)+rdln1_5);
// t:=trunc(v);
t:= trunc(n*rdt_n - 1.25); [/code:1]
If that seems risky, then this may help - for each solution found, I added j - t (total j values checked) and subtracted n - j (values skipped). The grand total got big pretty fast. Meaning most of the j solutions are much closer to n than to t. So start at j := n - 1, and descend to t. This makes the remaining improvements much easier.

This gets a little more involved. The basic idea is to fill the array as you go and rap around mod nm, overwriting the lowest value. This gives you a rolling list from (n - nm) to (n - 1). Then if (n-i, n-j, or n-r) < nm, use the array. If not, then recalculate (sqr(x)*x - x)/6.

The advantages are:
* An array of nm elements will work at full speed up to n = nm/0.789 ~= 1.267*nm. Now, 25% bigger!
* When the limit is reached, the program slows down instead of stopping. Ram is a speed trap, not a wall.
* For a sampling of big solutions instead of a complete list, check only within the array.
-- This will miss solutions where (n - j) > nm but runs at full speed.
-- Use this to quickly sample-search for members of list #3.

Disadvantages:
* You must use a[index mod nm], or increment a 'mod'ed index in parallel with your n, i, j, r, etc.
-- That and the range checking clutters up the inner loops.
* When you reach the nm limit, every non-solution checks every j past nm -- It slows down immediately.

Your algorithm is so fast when it stays inside the array that other tweaks are only for checking beyond the array. I'll post them later.

ps. WANTED LIST: n -> a + b, a >= b
1) n and a are prime. -- I suspect this is very small or empty.
2) n, a, b are all prime. -- I'm fairly certain this is empty.
3) n->a1+b1 & n->a2+b2 , a1<>a2. -- Almost positive this list is empty, but see 5.
4) n->a+b and n>1000 meg -- I can give you a sampling, but not a comprehensive list. ;)
5) n -> a + b + c (+ d + ...).
-- I posted part of this list above. I used n -> n2 + a, n2 -> b + c => n -> a + b + c.
-- { relative sizes of a, b, c, and n2 may vary. }
But n !-> (a + b) + c, and n !-> (a + c) + b. { " -> " is not associative. }

2003-08-30, 01:59	#35
Maybeso Aug 2002 Portland, OR USA 2·137 Posts	My version of Borland Pascal has a signed 64 bit float with fixed precision of 0 digits. ;) [edit] better description [/edit] Basically a signed 64 bit int with auto-rounding (which can be a pain). That was my main motivation for trying to build the middle pile from the base of the big pile. -- I can search to almost n = 2^31 for the big pile, with a max of n = 2^21 on the middle pile instead of on the sum. After I get my first overflow error, I'll put checks in. It should let me search n = 2^31 to 2^63 to an ever-decreasing depth. By dividing by 2 & 3 first, I can get really close. The pile sizes for n > 2meg found so far:[list]2132122 = 2130224 + 295722 2140708 = 1969230 + 1295380 2192458 = 2192428 + 75630 2207645 = 1911717 + 1556746 2209055 = 2203448 + 434230 2212429 = 1985945 + 1441763 2212748 = 2078068 + 1229878 2225894 = 2158023 + 992738 2240860 = 1930654 + 1594775[/list:u]The last line --> 1875398240518859420 = 1199396485472305120 + 676001755046554300 In that range, it checks 2.33 sizes per second. If c00ler includes the time it takes to build his array in his timings, It might tip the balance in favor the other methods, especially at n > 1.5 meg. I,ve tweaked my search to skip over bad sums. I tried these: 1. A silly pseudo square/cube-root with feedback - in an attempt to make an increasing sequence of tetrahedrals match my converging sum of triangles. The scary thing is it seems to work, but it uses 4 divides -- I wasn't sure how it compared. 2. A binary hop, which skips big gaps well, but with at least 4 compares per "row" or several conditionals. 3. Check mod 5, 10, or 20 and skip mismatches - mod 20 repeats, allowing a look-up table. This worked great (and works for your nested for-next method), but my pascal has very slow multi-dim array access. A pointer implementation may be the fastest. It turns out the fastest method was a binary hop on the first gap, and my silly hop on the remainder. (I tuned my hop to beat a binary search for either small gaps or big gaps, not both. still working on it.) I thought of another bounds optimization while writing this post, now if only I can remember it when I'm done. . .

2003-08-30, 08:46	#37
tom11784 Aug 2003 Upstate NY, USA 506₈ Posts	After writing an 11-line program it took less than 15 seconds to produce the following list: [code:1] 3 3 4 8 14 15 20 54 55 30 55 58 39 70 74 84 90 110 61 102 109 34 118 119 48 138 140 119 154 175 187 201 245 100 290 294 327 335 418 362 415 492 252 424 452 149 429 435 424 448 550 248 450 474 434 495 588 219 515 528 314 527 562 136 532 535 399 588 644 532 643 747 324 663 688 272 688 702 304 695 714 424 705 753 349 713 740 608 754 868 378 790 818 489 869 918 230 903 908 775 950 1098 968 1001 1241 878 1044 1220 703 1064 1158 922 1286 1428 855 1343 1450 290 1430 1434 367 1436 1444 1351 1478 1796 897 1621 1708 504 1629 1645 750 1690 1738 798 1818 1868 1609 1941 2256 1146 2072 2183 1139 2115 2220 438 2164 2170 1105 2303 2385 853 2417 2452 [/code:1] Can anyone refresh my memory on how to get Ubasic to print to a file instead of the screen?

2003-09-03, 20:02	#39
Maybeso Aug 2002 Portland, OR USA 2×137 Posts	Hey C00ler, Very Impressive! I ported your code with no trouble to BP, and it really screams. There is no way the other methods can compete in any range of significant size. : With just a small rolling array, I had it spit out some of the variables/ratios for certain conditions. see third item. Here are several improvements to try. I've never seen two solutions for a single n value. So I exit the inner loop after a solution is found. I printed out t/n and j/n for valid solutions. t/n seems to converge to 0.788xx, and I never saw j/n < 0.801. Any t value that works for n = 4 should be small enough.[code:1]const rdt_n : extended = 0.789; // limit of t/n. ... // ai:=a[i]; // u:=ai+sqrt(sqr(ai)-rd3); // v:=exp(rdln(u)+rdln1_5); // t:=trunc(v); t:= trunc(nrdt_n - 1.25); [/code:1] If that seems risky, then this may help - for each solution found, I added j - t (total j values checked) and subtracted n - j (values skipped). The grand total got big pretty fast. Meaning most of the j solutions are much closer to n than to t. So start at j := n - 1, and descend to t. This makes the remaining improvements much easier. This gets a little more involved. The basic idea is to fill the array as you go and rap around mod nm, overwriting the lowest value. This gives you a rolling list from (n - nm) to (n - 1). Then if (n-i, n-j, or n-r) < nm, use the array. If not, then recalculate (sqr(x)x - x)/6. The advantages are: An array of nm elements will work at full speed up to n = nm/0.789 ~= 1.267nm. Now, 25% bigger! When the limit is reached, the program slows down instead of stopping. Ram is a speed trap, not a wall. * For a sampling of big solutions instead of a complete list, check only within the array. -- This will miss solutions where (n - j) > nm but runs at full speed. -- Use this to quickly sample-search for members of list #3. Disadvantages: * You must use a[index mod nm], or increment a 'mod'ed index in parallel with your n, i, j, r, etc. -- That and the range checking clutters up the inner loops. * When you reach the nm limit, every non-solution checks every j past nm -- It slows down immediately. Your algorithm is so fast when it stays inside the array that other tweaks are only for checking beyond the array. I'll post them later. ps. WANTED LIST: n -> a + b, a >= b 1) n and a are prime. -- I suspect this is very small or empty. 2) n, a, b are all prime. -- I'm fairly certain this is empty. 3) n->a1+b1 & n->a2+b2 , a1<>a2. -- Almost positive this list is empty, but see 5. 4) n->a+b and n>1000 meg -- I can give you a sampling, but not a comprehensive list. ;) 5) n -> a + b + c (+ d + ...). -- I posted part of this list above. I used n -> n2 + a, n2 -> b + c => n -> a + b + c. -- { relative sizes of a, b, c, and n2 may vary. } But n !-> (a + b) + c, and n !-> (a + c) + b. { " -> " is not associative. }