On Fri, Mar 20, 2015 at 11:49 AM, Bill Gosper <billgosper@gmail.com> wrote:
HGBaker> Some non floating point units of computational effort:
Bitcoin POW (SHA-256 hashes/second)
Other POW's https://en.wikipedia.org/wiki/Proof-of-work_system
Password cracking
Most of these problems are "embarrassingly parallel".
Perhaps someone here has some ideas for a non-embarrassingly-parallel unit of computational effort.
<hgb
How about the Minsky Stock Index?
Oops, Neil Bickford has found a long-sought algorithm to parallelize the Minsky Circle Recurrence, and noted funster Tom Rokicki (diameter(Rubik group)=20) is excitedly throwing GPUs at it.
Subj: What is the period of this integer sequence? On Sun, May 4, 2014 at 10:37 AM, Bill Gosper <billgosper@gmail.com> wrote:
0, 1, 7, -2, -8, 3, 14, -4, -16, 5, 21, -6, -24, 7, 28, -7, -25, 7, 27, -7, -26, 7, 26, -6, -19, 5, 18, -4, -12, 3, 10, -2, -5, 1, 2, 0, 2, -1, -6, 3, 16, -5, -22, 7, 30, -8, -30, 8, 30, -7, -23, 6, 22, -5, -16, 4, 14, -3, -9, 2, 6, -1, -2, 1, 5, -1, -3, 1, 4, -1, ...
a[0] = 0; a[1] = 1; a[k_?OddQ] := a[k] = a[k - 2] - Floor[9*a[k - 1]/17]; a[k_?EvenQ] := a[k] = a[k - 2] + Floor[15*a[k - 1]/2]
This is the "Minsky Stock Index" that Corey and Julian ran fruitlessly from a[-10^14] to a[10^14] a few years ago. "If you haven't looked at a problem in the last few years, you haven't looked at it." --Ed Pegg, Jr. There is a slight chance that the period is infinite. (When it reached 18 trillion, we exclaimed AT&T!)
The above recursive definition crashes Mathematica in under a million, even with memoizing. Instead use the iteration In[115]:= NestList[Function[xy, {#, xy[[2]] + Floor[15*#/2]} & [xy[[1]] - Floor[9*xy[[2]]/17]]], {1, 0}, 35] e.g., for {a[-1],a[0}, {a[1],a[2]},...{a[69],a[70]} Out[115]= {{1, 0}, {1, 7}, ..., {-1, -4}}
~100 times faster: Clear[MinskyStepC];(*No frills*) MinskyStepC[x0_Integer, y0_Integer, d_Integer | d_Rational, e_Integer | e_Rational, n_] := minskystepc[x0, y0, Numerator[d], Denominator[d], Numerator[e], Denominator[e], n]; minskystepc = Compile[{{x0, _Integer}, {y0, _Integer}, {dn, _Integer}, {dd, _Integer}, {en, _Integer}, {ed, _Integer}, {ct, _Integer}}, Module[{x = x0, y = y0}, Do[x = x - Quotient[y*dn, dd]; y = y + Quotient[x*en, ed], {ct}]; {x, y}], RuntimeOptions -> "Speed", CompilationTarget -> "C"]; E.g., (Corey's old) In[925]:= MinskyStep[1, 0, 9/17, 15/2, 10^7] // tim 60.579526,2 Out[925]= {-11142, -46828} In[926]:= MinskyStepC[1, 0, 9/17, 15/2, 10^7] // tim 0.634458,2 Out[926]= {-11142, -46828}
Background: http://www.blurb.com/books/2172660-minskys-trinskys-3rd-edition Unlike Collatz or twin prime searching, this is a very specific question about very specific quantities, rather than a question about the infinitude of integers. --rwg
So far, nobody(?) has figured out how to distribute this calculation.
Until now.
I conjecture finitude for all these monsters that don't blow right up with an obvious, provable pattern. The bigger they get, the proportionally smaller is the effect of the Floor steps, and thus the closer they get to pure ellipses. I.e. their growth rate slows down, and the density of points they visit will increase with increasing radius. Eventually they will run out of new points, and thus must return to the beginning, by reversibility.
But maybe not this week. Tom's crunch has so far pushed Corey's & Julian's 208T to 3.227P, while the circularized radius has nearly tripled. Meanwhile, as spinoff from Neil's algorithm, Tom has found a loop with these same multipliers (9/17, 15/2) of length 389T, roughly seven times the previous record for any Minsky loop. Thus, the "population" increased 30fold while the "radius" only tripled. Thus (unless I'm spazzing) the point density is increasing with time, which predicts convergence unless the rate of increase approaches zero. Which is not happening. Here is Tom's latest news, which I hope he won't mind me blabbing. The startling proximity of the current extremal points is an artifact of the search algorithm. When Neil and I first saw this, we thought Tom was April Fooling. ------------ So things have been running a bit over five days. At the moment, from (1,0), we are at forward 35432432 172100384 774871328665934 backward 35451612 172193544 -2452403557917764 so in total that's about 3.227P without looping. But that's not to say we haven't found some big loops!
From 1,003,636*(7,34) we have a closed loop of 388,651,797,405,176 steps, for instance. There are many other large closed loops.
In total I've explored 1.6286e16 points. From these I have found 1842 closed loops totaling 8.71398e+14 points and 5735 yet unresolved open segments totaling 1.54146e+16 points (including our largest one from (1,0) that is about 20% of the total points). We have explored the continuations of about 5M distinguished points (the distinguished points are i*(7,34), i integer > 0). The minimum traversal from DP to DP without an intervening DP is from 189*(7,34) to 187*(7,34) in 311 steps; the largest is from 4,567,906*(7,34) to 4,553,980*(7,34) in 76,299,044,924 steps.
From a small experiment it appears that the set of all points reached from or to a distinguished point is > 99.5% of all points; this is based on a few hundred million points near the center. As we expand away from the center, points that traverse to or from a DP appear to decrease in absolute density. But most of the really short loops never get to a DP.
It's quite possible some distinguished point may iterate and never come back to the set of distinguished points, but that has not happened yet from exploring more than the first five million distinguished points. If I were to start this again, I'd probably pick a different set of distinguished points (like i*(0,1)) for better coverage and to improve the efficiency of the kernel slightly. But I've decided not to restart my existing kernel. The core idea---distinguishing points and exploring their futures in parallel---I got from Neil; everything else is just a tiny bit of hacking. -tom ---------- --rwg