On 19.04.2017 21:32, H. S. Teoh via Digitalmars-d wrote:
I alluded to this in D.learn some time ago, and finally decided to take
the dip and actually write the code. So here it is: exact arithmetic
with numbers of the form (a+b√r)/c where a, b, c are integers, c!=0, and
r is a (fixed) square-free integer.
Code: https://github.com/quickfur/qrat
...
Nice. :)
Some suggestions:
- You might want to support ^^ (it is useful for examples like the one
below).
- constructor parameter _b should have a default value of 0.
- formatting should special case b==-1 like it special cases b==1.
(also: as you are using Unicode anyway, you could also use · instead
of *. Another cute thing to do is to add a vinculum.)
Example application: Computing large Fibonacci numbers efficiently:
import qrat;
import std.bigint;
alias ℕ=BigInt;
enum φ=(1+surd!(5,ℕ))/2,ψ=(1-surd!(5,ℕ))/2;
auto pow(T,S)(T a,S n){
T r=T(ℕ(1),ℕ(0));
for(auto x=a;n;n>>=1,a*=a)
if(n&1) r*=a;
return r;
}
auto fib(long n){
return (pow(φ,n)-pow(ψ,n))/surd!(5,ℕ);
}
void main(){
import std.stdio;
foreach(i;0..40) writeln(fib(i));
writeln(fib(100000));
}
