Very High Precision Floating-Point

[Neo]

Sound like a problem in Number Theory. I know a few persons at Project Euler who are geniuses in that domain. Let me know if you ever need help.

It could definitely be considered a problem in number theory.  My guess is that it's harder than most problems on Project Euler, if only for that it's unsolved and may not have a solution, but it's similar in that determining solvability is probably NP-complete in the number of "simple" functions needed to represent the overall function.  I'd be happy for the help, though I have to get my honours project done first (about 5 days left).  :toothy

In case any of my friends from Carleton read this, no, it has nothing to do with Jit's coffee bet problem of shortest path through the Delaunay triangulation of points in convex position, though that would likely also involve pi.  That would be a pretty cool problem to solve, but it would only be worth a lifetime supply of coffee, which I don't drink.  :lol

not fair - you gave the French guy hints - lol

I made sure that Google Translate spits out pretty much exactly what I meant in English, just in case.  :U  It took a few tries, though, 'cause it's awfully hard to make it unambiguous to a translation program, and English-to-French would have been even harder if I had used it for that.

[Rockoon]

I've now done a little playing around with generating reciprocals, and it seems to me that for all finite integers 0 < X, that the base-2 expansion of 1/x is never both infinite and non-repeating ( I have not observed any invalidating evidence, but I have not proven it.)

Now, this says to me that it is possible to store all 1/X with perfect accuracy. Detecting the repetitions while performing the expansion seems trivial as well (the numerator (seems to) always cycles (back) to a 0 or 1, 0 meaning termination and 1 meaning repeating.)

But, it seems that simultaneously generating and then multiplying by these reciprocals has the same time complexity as a multiplication all by itself.. which leads me to wonder how many algorithms actualy need the reciprocal, instead of the product of the reciprocal and another number.

[FORTRANS]

Hi,

   As opposed to true floating point, would fixed point work?  A
quick fixed point, four function library should be easy.  Hmm,
sounds like another project for this weekend.  The hardest part
would seem to be a decimal display routine, and I have an ugly
version in my fixed point to binary program.

Regards,

Steve N.

edit:  Should say fixed point to decimal.
SRN

[dedndave]

hiya Steve and Rockoon

Now, this says to me that it is possible to store all 1/X with perfect accuracy.

it is a bit like looking at a ruler with 16ths and 32nds of an inch

binary  decimal
0.1      0.5
0.01     0.25
0.001    0.125
0.0001   0.0625
and so on

all binary fractions that we use for programming are made up of sums of these types of values

it seems to me that for all finite integers 0 < X, that the base-2 expansion of 1/x is never both infinite and non-repeating

hold on - there are very, very many repeating and infinite values to be found
1/7 is always a good one that comes to mind
the only way to get it to stop is to express it in a radix that has 7 as a factor
1/7 expressed in base 7 is 0.1

1/3, 1/11, 1/13, 1/17
these are all reciprocals of primes
unless the radix has that prime as a factor, the number will be a "run-on"

notice that base 10 has 2 as a factor - it's that dang 5 that makes binary math fun   :bg

[Rockoon]

it is a bit like looking at a ruler with 16ths and 32nds of an inch

binary  decimal
0.1      0.5
0.01     0.25
0.001    0.125
0.0001   0.0625
and so on

umm, no kidding?

it seems to me that for all finite integers 0 < X, that the base-2 expansion of 1/x is never both infinite and non-repeating

hold on - there are very, very many repeating and infinite values to be found

Please re-read what you quoted (and that I quoted again)

1/7 is always a good one that comes to mind
the only way to get it to stop is to express it in a radix that has 7 as a factor
1/7 expressed in base 7 is 0.1

and expressed in base-2 it is .001 repeating, and thus is not an infinite expansion that is also non-repeating.

If you re-read what I was writing, you will see that I full well understand this all and noted that all the expansions are most probably either finite or repeating (the generator is all linear, after all), and that detecting these repeates is easy. It falls right out of at least one algorithm that expands 1/x...