Exact arithmetic with quadratic irrationals

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Wed Apr 19 13:47:04 PDT 2017


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));
}




More information about the Digitalmars-d mailing list