99 lines
2.0 KiB
Perl
99 lines
2.0 KiB
Perl
package Manticore::Num::ContinuedFraction;
|
|
|
|
# lazy and potential infinite continued fraction
|
|
|
|
use strict;
|
|
use warnings;
|
|
|
|
use Math::BigRat;
|
|
use Data::Dumper;
|
|
|
|
### Methods and constructor
|
|
# Approximation object:
|
|
# {
|
|
# a => BigRat, this integer
|
|
# r => remainder, input number; undef if fraction has ended
|
|
# c => child, better approximation (or undef)
|
|
# e => end of list?
|
|
# }
|
|
sub new {
|
|
my ($pkg, $x) = @_;
|
|
die "ContinuedFraction can only be constructed of positive numbers!" if $x<0;
|
|
my $prop = int $x;
|
|
#if(0 == $prop) {
|
|
# return undef; # TODO
|
|
#}
|
|
my $rem = $x - $prop;
|
|
return bless {
|
|
a => $prop,
|
|
r => $rem,
|
|
}
|
|
}
|
|
|
|
sub child {
|
|
my $self = shift;
|
|
if(not $self->{c}) {
|
|
my ($a, $r) = @{$self}{qw(a r)};
|
|
if(0 == $r) {
|
|
return undef
|
|
}
|
|
my $c = Manticore::Num::ContinuedFraction->new(1/$r);
|
|
$self->{c} = $c;
|
|
}
|
|
return $self->{c}
|
|
}
|
|
|
|
sub firstk {
|
|
my ($self, $k) = @_;
|
|
if($k <= 0) {
|
|
return []
|
|
} else {
|
|
my $c = $self->child();
|
|
return [$self->{a}] unless defined $c;
|
|
my $l = $c->firstk($k-1);
|
|
unshift @$l, $self->{a};
|
|
return $l
|
|
}
|
|
}
|
|
|
|
# take the common start part, but at most k parts
|
|
sub commonk {
|
|
my ($self, $other, $k) = @_;
|
|
if($k <= 0) {
|
|
return []
|
|
} else {
|
|
return [] if $self->{a} != $other->{a};
|
|
my $c = $self->child();
|
|
my $d = $other->child();
|
|
return [$self->{a}] unless defined $c;
|
|
my $l = $c->commonk($d, $k-1);
|
|
unshift @$l, $self->{a};
|
|
return $l
|
|
}
|
|
}
|
|
|
|
### Functions
|
|
# list of integers -> bigrat
|
|
sub reconstruct {
|
|
my $l = shift;
|
|
my $ret = Math::BigRat->new($l->[-1]);
|
|
for(reverse (0..$#$l-1)) {
|
|
$ret = $l->[$_] + 1/$ret
|
|
}
|
|
return $ret;
|
|
}
|
|
|
|
# round to bigRat with ContinuedFraction of $steps parts
|
|
sub roundSteps {
|
|
my ($steps, $x) = @_;
|
|
#print "[[ $steps -- $x ]]\n";
|
|
return Math::BigRat->new(0) if 0==$x;
|
|
my $sgn = $x < 0 ? -1 : 1;
|
|
my $cf = Manticore::Num::ContinuedFraction->new($sgn*$x);
|
|
#print Data::Dumper::Dumper($cf);
|
|
my $l = $cf->firstk($steps);
|
|
return reconstruct($l)*$sgn;
|
|
}
|
|
|
|
1;
|