converting _Rounded_ percentage Number to a simple fraction -- e.g. 56%

[Hen Hanna]

converting _Rounded_ percentage Number to a simple fraction -- e.g. 56%
---------- i checked to see if such a Tool already exists, and apparently there isn't.


when/if i hear that [ 67% of respondents in the Survey approved... ]
i'd wonder if there were only 3 or 6 or 9 ppl surveyed.


if the figure is 56% and i suspect a small sample population size,
what is the probable number ? (of the survey size) ?


this (a tool like this) seems like a nice programming exercise. HH

[Hen Hanna]

i wrote a little program to figure out 56%

-- is there a good general way to tackle/approach these ?


what simplest fraction would give 51% ?
what simplest fraction would give 52% ?
what simplest fraction would give 53% ?
what simplest fraction would give 54% ?
what simplest fraction would give 55% ?
what simplest fraction would give 56% ?
what simplest fraction would give 57% ?
what simplest fraction would give 58% ?
what simplest fraction would give 59% ?

--- it seems like something Martin Gardner would have written about.

[Hen Hanna]

maybe in a few years, Google will have this standard Tool -- [ Fraction Guesser ]

when you ask it -- what fraction is 51% ?

it will respond with


The simplest candidate is (18 Yes, 17 No) 18/35 = 51.4


(17 Yes, 16 No) 17/33 = 51.515151515151516
(18 Yes, 17 No) 18/35 = 51.42857142857142
(19 Yes, 18 No) 19/37 = 51.35135135135135

[Gene Wirchenko]

I have wondered about this myself. I came up with an iterative
solution. Roughly (untested code):

targetlow=.51375 example
targethigh=.51385 range

numerator=1
denominator=1

while numerator/denominator not in [targetlow,targethigh]
if numerator/denominator<targetlow
numerator=numerator+1
denominator=denominator+1

return numerator,denominator

Sincerely,

Gene Wirchenko

[Eric Sosman]

This is similar to an approach I once used on a Texas Instruments
programmable calculator almost half a century ago to guess baseball
batting histories (hits and at-bats) from early-season batting averages
(the ratio thereof). I used no termination condition; the gadget merely
paused and flashed numbers each time it found a better guess, then kept
on trying to improve it. I forget what happened if it hit the desired
ratio exactly.

A faint and far-off chime in a worn-out gray cell lost somewhere in
what remains of my brain says "continued fractions," with a notion that
they might lead to a better algorithm. YMMV.

--
eso...@comcast-dot-net.invalid
Six hundred three days to go.

[Phil Carmody]

Eric Sosman <eso...@comcast-dot-net.invalid> writes:
> On 5/28/2019 12:46 AM, Gene Wirchenko wrote:
> > On Sat, 25 May 2019 09:56:57 -0700 (PDT), Hen Hanna
> > <henh...@gmail.com> wrote:
> >
> >> On Saturday, May 25, 2019 at 9:48:08 AM UTC-7, Hen Hanna wrote:
> >>> On Saturday, May 25, 2019 at 9:35:48 AM UTC-7, Hen Hanna wrote:
> >>>> converting _Rounded_ percentage Number to a simple fraction -- e.g. 56%
> >>>> ---------- i checked to see if such a Tool already exists, and apparently there isn't.
> >>>>
> >>>>
> >>>> when/if i hear that [ 67% of respondents in the Survey approved... ]
> >>>> i'd wonder if there were only 3 or 6 or 9 ppl surveyed.
> >>>>
> >>>>
> >>>> if the figure is 56% and i suspect a small sample population size,
> >>>> what is the probable number ? (of the survey size) ?

> A faint and far-off chime in a worn-out gray cell lost somewhere in
> what remains of my brain says "continued fractions," with a notion that
> they might lead to a better algorithm. YMMV.

So it seems, if you want to arrive at the closest ratios, but that doesn't
give you all the answers you might be after.

Use of a binary chop down Farey sequences might be better?

e.g. 0.56, considered as the range 0.555-0.565, by hand:

Start with: [ 0/1 1/1 ]

[ 0/1 1/2 1/1 ]
1/2 is not in range, prune left
=> [ 1/2 1/1 ]

[ 1/2 2/3 1/1 ]
2/3 is not in range, prune right
=> [ 1/2 2/3 ]

[ 1/2 3/5 2/3 ]
3/5 is not in range, prune right
=> [ 1/2 3/5 ]

[ 1/2 4/7 3/5 ]
4/7 is not in range, prune right
=> [ 1/2 4/7 ]

[ 1/2 5/9 4/7 ]
5/9 is in range, output 5/9
no pruning

[ 1/2 6/11 5/9 9/16 4/7 ]
6/11 is not in range, prune left
9/16 is in range, output 9/16
=> [ 6/11 5/9 9/16 4/7 ]

[ 6/11 11/20 5/9 14/25 9/16 13/23 4/7 ]
11/20 is not in range, prune left
output 14/25 (no check needed - it's between 2 in range)
13/23 is not in range, prune right
=> [ 11/20 5/9 14/25 9/16 13/23 ]

[ 11/20 16/29 5/9 19/34 14/25 23/41 9/16 22/39 13/23 ]
16/29 is in range, output 16/29
output 19/34
output 23/41
22/39 is in range, output 22/39
=> [ 11/20 16/29 5/9 19/34 14/25 23/41 9/16 22/39 13/23 ]

...

It seems more heavyweight than brute force, but a lot of denominators
will never even be looked at, and because the termwise sum of any two
numbers in range is also in range, only the extremal new terms actually
need to be checked, so there's a slim possibility that it might be a win.
I suspect it would work best with more significant digits, as it should
home in reasonably quickly.

Phil
--
In order for there to be rights, there must be wrongs - if you want to
get rid of wrongs, which great leaders do, you *must* get rid of rights.

[Hen Hanna]

On Thursday, May 30, 2019 at 12:30:16 PM UTC-7, Phil Carmody wrote:

> Eric Sosman <> writes:
> > On 5/28/2019 12:46 AM, Gene Wirchenko wrote:
> > > On Sat, 25 May 2019 09:56:57 -0700 (PDT), Hen Hanna

[nerve comes from getting rid of nerves]


is there a Web page on this? --
what is the smallest square containing 3 9's?
what is the smallest square containing 4 9's?
what is the smallest square containing 5 9's?
..........


------- Why are Squares (with '9's) interesting, and not Cubes?
and why 9's and not other digits?

__________________________


thanks! when i thought of this, i had a hunch that it's related to the Fractal Snowflake, etc.

here it is:

https://upload.wikimedia.org/wikipedia/en/1/1d/Apolloinan_gasket_Farey.png

https://en.wikipedia.org/wiki/Farey_sequence

HH

[Phil Carmody]

Phil Carmody <pc+u...@asdf.org> writes:
> Use of a binary chop down Farey sequences might be better?

...
> It seems more heavyweight than brute force, but a lot of denominators
> will never even be looked at, and because the termwise sum of any two
> numbers in range is also in range, only the extremal new terms actually
> need to be checked, so there's a slim possibility that it might be a win.
> I suspect it would work best with more significant digits, as it should
> home in reasonably quickly.

Pfft, other stuff I should be doing is boring, let's find out...

============ 8< begin -- fareyprox.pl =====================
#!/usr/bin/perl -w

my ($int,$frac) = ($ARGV[0] =~ m/(\d*)\.(\d+)/);
$frac//die;
my $digits=length($frac);
my $denom=10**$digits;
my $lower=($frac-0.5)/$denom;
my $upper=($frac+0.5)/$denom;
printf("Searching for $int.$frac, treating as $int + [$lower,$upper]\n");
$frac=$frac/$denom;

my @ns=(0,1);
my @ds=(1,1);

print("Starting with: "); pretty(\@ns, \@ds);

my ($sums,$cmps)=(0,0);

# Early days, just have one range, binary chop it.
while(scalar(@ns)==2) {
my $nn = $ns[0]+$ns[1];
my $nd = $ds[0]+$ds[1];
$sums+=2;
print("\n[ $ns[0]/$ds[0] $nn/$nd $ns[1]/$ds[1] ]\n");
if($nn/$nd < $lower) {
$cmps--;
print("$nn/$nd is not in range, prune left\n");
$ns[0]=$nn;
$ds[0]=$nd;
} elsif($nn/$nd > $upper) {
print("$nn/$nd is not in range, prune right\n");
$ns[1]=$nn;
$ds[1]=$nd;
} else {
print("$nn/$nd is in range\n");
printf("%i/%i = %0.*f\n", $nn,$nd, $digits+3, $nn/$nd);
splice(@ns,1,0,$nn);
splice(@ds,1,0,$nd);
# and break...
}
$cmps+=2;
print("=> "); pretty(\@ns, \@ds);
print("work=$sums sums, $cmps cmps\n");
}
# With one guaranteed mid-point in the range, we're now doubling our
# array length each time through the loop, only pruning max 1 from
# each end.
while(1) {
my @nn = map { $ns[$_>>1] + ($_&1 ? $ns[($_+1)>>1] : 0) } (0..$#ns*2);
my @nd = map { $ds[$_>>1] + ($_&1 ? $ds[($_+1)>>1] : 0) } (0..$#ds*2);
$sums+=$#ns*2;
print("\n"); pretty(\@nn, \@nd);
my $shift=0;
if($nn[1]/$nd[1] < $lower) {
print("$nn[1]/$nd[1] is not in range, prune left\n");
$shift=1;
} else {
print("$nn[1]/$nd[1] is in range\n");
printf("%i/%i = %0.*f\n", $nn[1],$nd[1], $digits+3, $nn[1]/$nd[1]);
}
my $i=1;
while(($i+=2) < $#nn-2) {
printf("%i/%i = %0.*f\n", $nn[$i],$nd[$i], $digits+3, $nn[$i]/$nd[$i]);
}
if($nn[$i]/$nd[$i] > $upper) {
print("$nn[$i]/$nd[$i] is not in range, prune right\n");
--$i;
} else {
print("$nn[$i]/$nd[$i] is in range\n");
printf("%i/%i = %0.*f\n", $nn[$i],$nd[$i], $digits+3, $nn[$i]/$nd[$i]);
}
$cmps+=2;
@ns=splice(@nn,$shift,$i+2-$shift);
@ds=splice(@nd,$shift,$i+2-$shift);
print("=> "); pretty(\@ns, \@ds);
print("work=$sums sums, $cmps cmps\n");
}

sub pretty
{
my ($ns,$ds)=@_;
print("[", (map{" $ns->[$_]/$ds->[$_]"}(0..$#$ns)), " ]\n");
}

============ 8< end -- fareyprox.pl =====================

phil@razspaz:/tmp$ ./fareyprox.pl 3.14159

Searching for 3.14159, treating as 3 + [0.141585,0.141595]
Starting with: [ 0/1 1/1 ]

[ 0/1 1/2 1/1 ]
1/2 is not in range, prune right
=> [ 0/1 1/2 ]
work=2 sums, 2 cmps

[...]

[ 14/99 15/106 1/7 ]
15/106 is not in range, prune left
=> [ 15/106 1/7 ]
work=42 sums, 27 cmps

[ 15/106 16/113 1/7 ]
16/113 is in range
16/113 = 0.14159292
=> [ 15/106 16/113 1/7 ]
work=44 sums, 29 cmps

[ 15/106 31/219 16/113 17/120 1/7 ]
31/219 is not in range, prune left
17/120 is not in range, prune right
=> [ 31/219 16/113 17/120 ]
work=48 sums, 31 cmps

[...
that 16/113 will never be pruned, so denominators are now guaranteed
to increment by at least 113 at every step
...]

[ 143/1010 159/1123 16/113 145/1024 129/911 ]
159/1123 is in range
159/1123 = 0.14158504
145/1024 is not in range, prune right
=> [ 143/1010 159/1123 16/113 145/1024 ]
work=80 sums, 47 cmps

[ 143/1010 302/2133 159/1123 175/1236 16/113 161/1137 145/1024 ]
302/2133 is not in range, prune left
175/1236 = 0.14158576
161/1137 is not in range, prune right
=> [ 302/2133 159/1123 175/1236 16/113 161/1137 ]
work=86 sums, 49 cmps

[...]

In the thousands already, so superficially it seems to be asymptotically
better than brute force. However, it's finding them massively out of order.

By the time it's spitting out only denominators greater than:
287/2027 = 0.14158855
it has done
work=622 sums, 63 cmps
and it's already started looking as deep as
5742/40555 = 0.14158550.
and just to do one more round takes it to
work=1138 sums, 65 cmps
which means the work is growing exponentially for only linear more progress.
Worse than brute force!

However, that's because I'm not throwing away fractions that have become
useless. Any fraction whose denominator exceeds a limit value (say $denom),
should be discarded immediately, and its neighbours marked as no longer
participating in that direction. Only sums where both sides are participating
towards each other should be performed (and any fraction who loses his 2nd
neighbour should also be discarded.

Anyone wanna code that up to see if it's a nett win in the long run?