Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread H. S. Teoh via Digitalmars-d
On Thu, Apr 20, 2017 at 09:11:56PM +0200, Timon Gehr via Digitalmars-d wrote: > On 20.04.2017 20:29, H. S. Teoh via Digitalmars-d wrote: [...] > > Having said that, I haven't scrutinized the performance > > characteristics of QRat too carefully just yet -- there is probably > > room for

Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 21:18, Timon Gehr wrote: On 20.04.2017 21:11, Timon Gehr wrote: Update: QRat now supports ^^. :-) Integral exponents only, of course. I also implemented negative exponents, because QRat supports division and the same algorithm can be easily reused for that purpose. ... Nice! :)

Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 21:11, Timon Gehr wrote: Update: QRat now supports ^^. :-) Integral exponents only, of course. I also implemented negative exponents, because QRat supports division and the same algorithm can be easily reused for that purpose. ... Nice! :) It does not work with BigInt-based

Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 20:29, H. S. Teoh via Digitalmars-d wrote: On Thu, Apr 20, 2017 at 02:51:12PM +0200, Timon Gehr via Digitalmars-d wrote: On 20.04.2017 03:00, H. S. Teoh via Digitalmars-d wrote: On Thu, Apr 20, 2017 at 02:01:20AM +0200, Timon Gehr via Digitalmars-d wrote: [...] Yes, there is in

Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread H. S. Teoh via Digitalmars-d
On Thu, Apr 20, 2017 at 02:51:12PM +0200, Timon Gehr via Digitalmars-d wrote: > On 20.04.2017 03:00, H. S. Teoh via Digitalmars-d wrote: > > On Thu, Apr 20, 2017 at 02:01:20AM +0200, Timon Gehr via Digitalmars-d > > wrote: > > [...] > > > Yes, there is in fact a beautifully simple way to do

Re: Exact arithmetic with quadratic irrationals

2017-04-20 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 03:00, H. S. Teoh via Digitalmars-d wrote: On Thu, Apr 20, 2017 at 02:01:20AM +0200, Timon Gehr via Digitalmars-d wrote: [...] Yes, there is in fact a beautifully simple way to do better. :) ... Ahh, so *that's* what it's all about. I figured that's what I was missing. :-D

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread H. S. Teoh via Digitalmars-d
On Thu, Apr 20, 2017 at 02:01:20AM +0200, Timon Gehr via Digitalmars-d wrote: [...] > Yes, there is in fact a beautifully simple way to do better. :) > > Assume we want to compute some power of x. With a single > multiplication, we obtain x². Multiplying x² by itself, we obtain x⁴. > Repeating

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 02:01, Timon Gehr wrote: My last post includes an implementation of this algorithm. ;) But in that implementation I used the parameter 'a' instead of the variable 'x' as a result of being tired, which makes it slightly more confusing than necessary even though it is correct.

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread Timon Gehr via Digitalmars-d
On 20.04.2017 02:01, Timon Gehr wrote: To get the formula for multiplicative inverses, one possible algorithm is: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm Better reference:

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread Timon Gehr via Digitalmars-d
On 19.04.2017 23:39, H. S. Teoh via Digitalmars-d wrote: On Wed, Apr 19, 2017 at 10:47:04PM +0200, Timon Gehr via Digitalmars-d wrote: 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

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread H. S. Teoh via Digitalmars-d
On Wed, Apr 19, 2017 at 10:47:04PM +0200, Timon Gehr via Digitalmars-d wrote: > 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

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread Timon Gehr via Digitalmars-d
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)

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread H. S. Teoh via Digitalmars-d
On Wed, Apr 19, 2017 at 07:54:02PM +, Stanislav Blinov via Digitalmars-d wrote: > Awesome! Congrats and thanks for sharing. > > On Wednesday, 19 April 2017 at 19:32:14 UTC, H. S. Teoh wrote: > > > Haha, it seems that the only roadblocks were related to the > > implementation quality of

Re: Exact arithmetic with quadratic irrationals

2017-04-19 Thread Stanislav Blinov via Digitalmars-d
Awesome! Congrats and thanks for sharing. On Wednesday, 19 April 2017 at 19:32:14 UTC, H. S. Teoh wrote: Haha, it seems that the only roadblocks were related to the implementation quality of std.numeric.gcd... nothing that a few relatively-simple PRs couldn't fix. So overall, D is still

Exact arithmetic with quadratic irrationals

2017-04-19 Thread H. S. Teoh via Digitalmars-d
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 I