|
Re: Percentages to Fractions
by Roger (Parson) on Feb 03, 2004 at 13:59 UTC
|
Not to discourage you, but you really need a more efficient algorithm. Your algorithm is O^2 at best, and as the need for accuracy increases, the performance penalty gets greater and greater.
Here's an alternative very fast and efficient log(log(O)) algorithm: A fraction can be expressed as the sum (or difference) of a series of fractions:
0.35 = 1/28 - 1/6 - 1/60 = 7/20
0.35 = int (1/0.35) - int (1/(1 - int(1/0.35))) ...
Which is a perfect candidate for a recursive function. I implement the following demo to show how this can be done. Hopefully you might find it useful. :-)
use strict;
use warnings;
while (<DATA>) {
chomp;
my ($den, $div, $error) = fraction($_);
print "$_\t$den/$div\n";
}
sub fraction
{
my $value = shift;
my $a = 1;
my $b = int(1 / $value);
my $c = (1 / $b) - $value; # error
return ($a, $b, $c) if $c < 0.0005;
my ($d, $e, $f) = fraction($c);
my $g = $a * $e - $d * $b;
my $h = $b * $e;
for (2,3,5,7) { # reduces 2/4 => 1/2, 3/27 => 1/9, etc.
($g, $h) = reduce($g, $h, $_);
}
return ($g,
$h,
$f);
}
sub reduce
{
my ($a, $b, $base) = @_;
while ($a % $base == 0 && $b % $base == 0) {
$a = $a / $base;
$b = $b / $base;
}
return ($a, $b);
}
__DATA__
0.035
0.037
0.039
0.041
0.043
0.046
0.048
0.058
0.068
0.078
0.35
0.37
0.39
0.41
0.43
0.46
0.48
0.58
0.68
0.78
And the output -
0.035 7/200
0.037 1/27
0.039 974/24975
0.041 41/1000
0.043 1/23
0.046 596/12957
0.048 479/9980
0.058 1197/20638
0.068 277/4074
0.078 175/2244
0.35 7/20
0.37 57/154
0.39 6311/16182
0.41 4961/12100
0.43 43/100
0.46 23/50
0.48 47/98
0.58 2081/3588
0.68 151/222
0.78 103/132
| [reply]
[d/l]
[select] |
|
|
Did you look at the link provided to Continued Fractions?
Sure, the approach there is more complex, but the method provided does a better job of producing a rapidly converging sequence of fractional approximations than yours does. Modifying it to stop when the next approximation is more than 100, I produce the following output on your dataset:
2/57 = 0.0350877192982456
1/27 = 0.037037037037037
3/77 = 0.038961038961039
3/73 = 0.0410958904109589
4/93 = 0.043010752688172
4/87 = 0.0459770114942529
1/21 = 0.0476190476190476
4/69 = 0.0579710144927536
3/44 = 0.0681818181818182
6/77 = 0.0779220779220779
7/20 = 0.35
37/100 = 0.37
39/100 = 0.39
41/100 = 0.41
43/100 = 0.43
23/50 = 0.46
12/25 = 0.48
29/50 = 0.58
17/25 = 0.68
39/50 = 0.78
For half of them it found the actual fraction. For the other half it was never off by more than 0.0001. If you let it go to a denominator of 1000, it correctly identified every fraction, and put it in lowest terms.
(There are other tricks that I used there, like a GCD algorithm that is completely general and more efficient than trial division.) | [reply]
[d/l] |
|
|
$ perl fract.pl 1.61803398874989
2/1 err=0.38196601125011
3/2 err=0.11803398874989
5/3 err=0.0486326779167767
8/5 err=0.0180339887498899
13/8 err=0.00696601125010998
21/13 err=0.0026493733652746
34/21 err=0.00101363029772905
55/34 err=0.00038692992636058
89/55 err=0.000147829431928148
144/89 err=5.6460660002422e-05
233/144 err=2.15668056655627e-05
377/233 err=8.23767692859079e-06
610/377 err=3.14652862454246e-06
987/610 err=1.20186464402927e-06
1597/987 err=4.59071791913956e-07
2584/1597 err=1.75349764708344e-07
4181/2584 err=6.69776640815911e-08
6765/4181 err=2.55831835715981e-08
10946/6765 err=9.77191327855564e-09
17711/10946 err=3.73253206120694e-09
28657/17711 err=1.42570710792711e-09
46368/28657 err=5.44565059712454e-10
75025/46368 err=2.08012052027584e-10
121393/75025 err=7.94468935083614e-11
196418/121393 err=3.03526093148321e-11
317811/196418 err=1.15869536188029e-11
514229/317811 err=4.43245440351347e-12
832040/514229 err=1.68642877440561e-12
1346269/832040 err=6.50812737035267e-13
2178309/1346269 err=2.41806574763359e-13
3524578/2178309 err=9.9031893796564e-14
5702887/3524578 err=3.10862446895044e-14
9227465/5702887 err=1.86517468137026e-14
14930352/9227465 err=4.44089209850063e-16
Lovely pattern! (Except that it wanders off into lala land after that last line...) | [reply]
[d/l] |
Re: Percentages to Fractions
by ysth (Canon) on Feb 03, 2004 at 16:33 UTC
|
Here's how I would do it:
use warnings;
use strict;
my $number = shift;
my $error = $number+1;
my $denom = 1;
while ($error) {
my $num = int($number * $denom + .5);
if (abs($num/$denom - $number) < $error) {
$error = abs($num/$denom - $number);
print "$num/$denom\t\terr=$error\n";
}
exit if ++$denom > 999;
}
Sample output:
$ perl fract.pl 3.14159265358979323
3/1 err=0.141592653589793
13/4 err=0.108407346410207
16/5 err=0.0584073464102071
19/6 err=0.0250740130768734
22/7 err=0.00126448926734968
179/57 err=0.00124177639681067
201/64 err=0.000967653589793116
223/71 err=0.000747583167258092
245/78 err=0.000567012564152147
267/85 err=0.000416183001557879
289/92 err=0.000288305763706198
311/99 err=0.000178512175651679
333/106 err=8.32196275291075e-05
355/113 err=2.66764189404967e-07
That last (355/113) is actually an extremely good value; you don't get better until:
52163/16604 err=2.66213257216208e-07
| [reply]
[d/l]
[select] |
Re: Percentages to Fractions
by jmcnamara (Monsignor) on Feb 03, 2004 at 13:56 UTC
|
Here is a simple fraction function that sometimes returns the right value. ;-)
#!/usr/bin/perl -wl
use strict;
sub fract {
%_=(%_,$_[0],$%);
~~%_
}
print fract(0.1250);
print fract(0.2500);
print fract(0.3750);
print fract(0.5000);
print fract(0.6249);
print fract(0.7510);
print fract(0.8750);
__END__
Prints:
1/8
2/8
3/8
4/8
5/8
6/8
7/8
Update: This is just a joke and apparently not a very good one. Don't use this code.
--
John.
| [reply]
[d/l] |
|
|
I feel an urge to explain how &fract works or rather doesn't work, especially since it's the first reply.
The function is complete bogus. It doesn't bother at all which argument it gets (as long as it hasn't been given before). What it does is to populate a hash and then stringify it, returning a string "$used_buckets/$allocated_buckets" (a buckets isn't equal to a value). More on this is in the perldata manual, but here's the relevant excerpt.
If you evaluate a hash in scalar context, it returns false if the hash is empty. If there are any key/value pairs, it returns true; more precisely, the value returned is a string consisting of the number of used buckets and the number of allocated buckets, separated by a slash. -- perldata 5.8.0
The line
%_=(%_,$_[0],$%);
works like
$_{$_[0]} = $%;
except the latter is more efficient and doesn't copy the hash over and over again. I guess why it was written like that was to try to make it non-obvious at a first glance that it uses an accumulating global variable.
The $% variable happens to be a special variable but that's quite irrelevant. It could've been mostly any scalar and I can only assume that $% was chosen because of the obfuscation effect. However, as I pointed out here, the hash algorithm sometimes share values and hence sometimes just uses one bucket, making the function not work as intended.
The ~~ is actually the unary operator ~ applied twice. ~ is bitwise negation, and if you doubly negate you get the original back. The side-effect is that you put the operand in scalar context, which is what's used here.
ihb
| [reply]
[d/l]
[select] |
|
|
This is slightly off-topic but I can't resist expressing my dislike for this post to which I'm replying. Writing a bogus routine that seems to do what's expected, even with test cases, and without strong indication that it's just a hoax as first reply to a serious question is just despicable. It contributes nothing but confusion. Sure, cute code can be fun but it should be in the right place. The first reply to a serious question is definately not the right place. Making it look like a serious reply doesn't make it any better. If one truly does want to contribute one would also include an explanation of how the cute code works. Otherwise it's just showoff.
The smilie and the "sometimes" hints you about it being bogus, but the "sometimes" can easily be interpreted as "it tries to make a qualified guess but sometimes fails" (in contrast of long, slow but working algorithms), especially since it provides several test cases. I can't blame any new Perl programmer that think "hey, cool, yet another guru trick" when looking at the above routine with all its, to the new Perler, new elements: %_, $%, and ~~. (Compare with the fairly common my $file = do { local (@ARGV, $/) = $filename; <> };, except that works.)
To broaden this post I'd like to encourage everyone to follow Ovid's (I believe, can't find the reference now) example of waiting a while for the question to be answered before posting cute solutions or getting into side-track discussions.
What scares me though is that the post has a fairly high reputation in comparison to the replies which provide solutions that actually work.
Just my thoughts,
ihb
| [reply]
[d/l]
[select] |
|
|
| [reply] |
Re: Percentages to Fractions
by David Caughell (Monk) on Feb 03, 2004 at 22:05 UTC
|
I'm replying to a bunch of people at once here...
Firstly, jmcnamara, I'm not sure exactly how that works, but it looks really neat. OOC, what does the ~~%_ do?
Just a general comment: My goal was to get something that approximates the truth, rather than represents it exactly. I would prefer 0.039 to be given as 1/25, rather than 974/24975, because I'm looking for "how many hands (roughly) out of 25 or less am I going to get what I'm looking for".
My code currently gives it as 1/23, which isn't very good at all, though! :)
I'm booted into Windows (and the downvotes flow in...) right now, so I'll tweak my code in a little bit, but I think that by narrowing the tolerance, I'd get a little closer to 1/25.
I like Roger's error/tolerance checking. It's much more elegant than what I've got. The reduction sub is pretty awesome too. I remember thinking about doing that, but I cheated by starting with the lowest denominators and numerators, and brute-forcing it, instead. That sub would be great to post to snippets though. :)
ysth, that's a sweet, sweet code. :)
| [reply] |
|
|
sub fract {
%_=(%_,$_[0],$%);
~~%_
}
This is bogus. $% is a built-in variable meaning "the current page number of the output." You could also write it as $_{$_[0]} = 1; which has a similar effect on the contents of the %_ hash.
The ~~%_ is the same as scalar(%_) because the ~ is the bitwise not. A hash in scalar context becomes a string representing the fraction of used hash buckets over the unused buckets.
| [reply]
[d/l]
[select] |
|
|
The $% just there for obfuscation, it could've been mostly any scalar -- that it's a built-in makes no difference -- as you indicated. However, "recent" optimizations involving shared values between keys makes it not generate the wanted result since the value is constant. For that, different values would be preferable, e.g. $_{$_[0]} = keys %_;.
Not that anyone ever should even think about using this.
ihb
| [reply]
[d/l]
[select] |
|
|
1/26 is closer to .039 than 1/25.
And thanks.
| [reply] |
|
|
Not that I want to encourage you to use Windows, but there is in fact a perl port for Windows that's really simple to install: http://www.activestate.com/
| [reply] |
Re: Percentages to Fractions (The good, the bad and the **rediculous**)
by Roger (Parson) on Feb 04, 2004 at 00:55 UTC
|
Ok, here's my rediculous approach that will give the exact answer... Thanks to tilly for the 'gcd' function, that was great! :-D
use strict;
use warnings;
while (<DATA>) {
chomp;
my $a = $_;
$a =~ s/^\d?\.0*?//; # strip 0.0 part from 0.035
my $b = length($_) - 2; # how many zero's we need
# assume in 0.0x form
my $c = 10 ** $b;
my $gcd = gcd($a, $c);
$a /= $gcd;
$c /= $gcd;
print $_, "\t", "$a/$c", "\n";
}
# ---- borrowed from tilly's code ----
sub gcd {
my ($n, $m) = @_;
while ($m) {
my $k = $n % $m;
($n, $m) = ($m, $k);
}
return $n;
}
__DATA__
0.035
0.037
0.039
0.041
0.043
0.046
0.048
0.058
0.068
0.078
0.35
0.37
0.39
0.41
0.43
0.46
0.48
0.58
0.68
0.78
And the output -
0.035 7/200
0.037 37/1000
0.039 39/1000
0.041 41/1000
0.043 43/1000
0.046 23/500
0.048 6/125
0.058 29/500
0.068 17/250
0.078 39/500
0.35 7/20
0.37 37/100
0.39 39/100
0.41 41/100
0.43 43/100
0.46 23/50
0.48 12/25
0.58 29/50
0.68 17/25
0.78 39/50
| [reply]
[d/l]
[select] |
|
|
How to convert a float to a fraction is a topic in Knuth's Concrete Mathematics. It is based on a wierd operation which one could call "children's fractional addition" (i.e. the way a child might add fractions). This is
a c a+c
--- + --- => -----
b d b+d
This is a very common children's mistake, and the result (until I saw this trick) is useful for nothing. But to find the sequence of best approximating fractions to any number, here is a bracketing algorithm based on the above operation which is fast and easy:
Algorithm to approximate x (a positive real number)
Start with two fractions:
a/b = 0/1
c/d = 1/0 [This is infinity, larger than any number]
create a third fraction e/f = (a+c)/(b+d) by "children adding" the two fractions Note: Do not simplify any fraction in this process. This new number will always be between the first two fractions. Discard one of the original two fractions, and replace it with the new fraction in such a way that the two fractions that are kept, still bracket the x.
Keep doing this and you will get a sequence of fractions that quickly squeeze the x.
It can be shown that no fraction with a smaller denominator can get closer than fractions in this sequence.
frac(3.14159265358979);
sub frac
{ my ($x,$a,$b,$c,$d,$e,$f) = (@_,0,1,1,0,1,1);
while ($f<1000)
{ if ($e<$x*$f) { ($a,$b) = ($e,$f) }
else { ($c,$d) = ($e,$f) }
($e,$f) = ($a+$c, $b+$d);
print "$a/$b < $x < $c/$d; => $e/$f\n";
} }
Produces the output
1/1 < 3.14159265358979 < 1/0; => 2/1
2/1 < 3.14159265358979 < 1/0; => 3/1
3/1 < 3.14159265358979 < 1/0; => 4/1
3/1 < 3.14159265358979 < 4/1; => 7/2
3/1 < 3.14159265358979 < 7/2; => 10/3
3/1 < 3.14159265358979 < 10/3; => 13/4
3/1 < 3.14159265358979 < 13/4; => 16/5
3/1 < 3.14159265358979 < 16/5; => 19/6
3/1 < 3.14159265358979 < 19/6; => 22/7
3/1 < 3.14159265358979 < 22/7; => 25/8
25/8 < 3.14159265358979 < 22/7; => 47/15
47/15 < 3.14159265358979 < 22/7; => 69/22
69/22 < 3.14159265358979 < 22/7; => 91/29
91/29 < 3.14159265358979 < 22/7; => 113/36
113/36 < 3.14159265358979 < 22/7; => 135/43
135/43 < 3.14159265358979 < 22/7; => 157/50
157/50 < 3.14159265358979 < 22/7; => 179/57
179/57 < 3.14159265358979 < 22/7; => 201/64
201/64 < 3.14159265358979 < 22/7; => 223/71
223/71 < 3.14159265358979 < 22/7; => 245/78
245/78 < 3.14159265358979 < 22/7; => 267/85
267/85 < 3.14159265358979 < 22/7; => 289/92
289/92 < 3.14159265358979 < 22/7; => 311/99
311/99 < 3.14159265358979 < 22/7; => 333/106
333/106 < 3.14159265358979 < 22/7; => 355/113
333/106 < 3.14159265358979 < 355/113; => 688/219
688/219 < 3.14159265358979 < 355/113; => 1043/332
1043/332 < 3.14159265358979 < 355/113; => 1398/445
1398/445 < 3.14159265358979 < 355/113; => 1753/558
1753/558 < 3.14159265358979 < 355/113; => 2108/671
2108/671 < 3.14159265358979 < 355/113; => 2463/784
2463/784 < 3.14159265358979 < 355/113; => 2818/897
2818/897 < 3.14159265358979 < 355/113; => 3173/1010
| [reply]
[d/l]
[select] |
|
|
| [reply] |
Re: Percentages to Fractions
by I0 (Priest) on Feb 22, 2004 at 05:29 UTC
|
use strict;
use POSIX;
sub cf{
my($v,$p) = @_;
my $i=int $v;
$v -= $i;
if( fabs($v)>$p ){
my($a,$n,$d)=cf(1/$v,$p*(1+abs$i));
return $i,$d,$a*$d+$n
}else{
return $i,0,1;
}
}
while( <DATA> ){
chomp;
my ($i,$n,$d) = cf($_,.001);
$n+=$i*$d;
print "$_:\t$n/$d\n";
}
__DATA__
0.035
0.037
0.039
0.041
0.043
0.046
0.048
| [reply]
[d/l] |
Re: Percentages to Fractions
by runentertain (Initiate) on Feb 21, 2004 at 06:35 UTC
|
| [reply] |