Rational Numbers

Thun uses only integers, no floating point, so how shall we implement functions like square root?

Numerical Tower

Following tradition, we will take one step up what is called the "numerical tower" and implement rational numbers.

... the numerical tower is a set of data types that represent numbers and a logic for their hierarchical organisation. (sic) Each type in the tower conceptually "sits on" a more fundamental type, so an integer is a rational number ... but the converse is not necessarily true ...

~ Numerical Tower

(See also Number System.)

Pairs of Integers

We will employ pairs of integers to form rational numbers (aka ℚ.) The numerator is expected to be below the denominator on the stack. E.g. one half would just be:

1 2

For example, we can represent, for all practical purposes, the number pi by the ratio between two integers:

884279719003555 281474976710656

To multiply a number by pi we can multiply by the numerator and then divide by the denominator:

joy? 10000 884279719003555 * 281474976710656 /
31415

To divide by pi we multiply by the denominator and then divide by the numerator:

joy? 31415 281474976710656 * 884279719003555 /
9999

Close enough?

≡ `scale`

[scale [mul] dip div] inscribe

Use scale to convert a ratio into an integer.

Any integer can be converted to a rational by putting 1 on the stack after it.

Arithmetic with Rational Numbers

Implementing the fundamental arithmetic operations is pretty straightforward:

(a, b) + (c, d) = (ad+bc, bd)
(a, b) - (c, d) = (ad-bc, bd)
(a, b) × (c, d) = (ac, bd)
(a, b) ÷ (c, d) = (ad, bc) with c != 0

~ Fractions in abstract mathematics

Multiplying Members of Two Rational Numbers

Starting with a b c d on the stack, with a b representing one ratio and c d the other as above...

For a × c we ditch b and d and then multiply:

pop popd mul

For a × d we ditch b and c and then multiply:

[popop] dip mul

For b × c we ditch a and d and then multiply:

pop mul popd

For b × d we ditch a and c and then multiply:

popd mul popd

So:

_ac pop popd mul
_ad [popop] dip mul
_bc pop mul popd
_bd popd mul popd

Computing in Parallel with `fork` and `cleft`

We can compute a × d and b × c in parallel with the fork combinator:

[_ad] [_bc] fork

Then we use add or sub to add or subtract the products:

_ad_bc [_ad] [_bc] fork

_ad+bc _ad_bc add
_ad-bc _ad_bc sub

For division we could also use _ad_bc and then discard the four arguments a b c d, but there is a variant of fork that already does that, cleft, so instead we just use that:

_div-frac [_ad] [_bc] cleft

Factoring `b × d`

Addition, subtraction, and multiplication all have b × d as the new denominator. We can factor the code to compute that into a definition that includes cleft, this new function expects the four arguments a b c d and a quoted program, it replaces these with the result of that quoted program and b × d computed in parallel (at least in theory. The current implementation of fork et. al. doesn't actually run in parallel. However, there is an experimental Python version that uses the fork system call to actually run in parallel.) Anyway, here's _/bd:

_/bd [_bd] cleft

That along with _ad+bc, _ad-bc, and _ac will allow us to implement addition, subtraction, and multiplication:

_add-frac [_ad+bc] _/bd
_sub-frac [_ad-bc] _/bd
_mul-frac [_ac] _/bd

That's really the only clever thing going on in the code.

Reducing

Because the arithmetic operations involve multiplication the terms will increase in magnitude. To counteract that we can reduce the rationals after each operation.

We can employ Euclid's Algorithm to compute the greatest common divisor between two integers:

true [tuck mod ?] loop pop

Here it is in action with 30 and 20:

                  30 20 • true [tuck mod ?] loop pop
             30 20 true • [tuck mod ?] loop pop
30 20 true [tuck mod ?] • loop pop
                  30 20 • tuck mod ? [tuck mod ?] loop pop
               20 30 20 • mod ? [tuck mod ?] loop pop
                  20 10 • ? [tuck mod ?] loop pop
             20 10 true • [tuck mod ?] loop pop
20 10 true [tuck mod ?] • loop pop
                  20 10 • tuck mod ? [tuck mod ?] loop pop
               10 20 10 • mod ? [tuck mod ?] loop pop
                   10 0 • ? [tuck mod ?] loop pop
             10 0 false • [tuck mod ?] loop pop
10 0 false [tuck mod ?] • loop pop
                   10 0 • pop
                     10 •

≡ `gcd`

[gcd true [tuck mod ?] loop pop] inscribe

We apply gcd with the nullary combinator so that it doesn't consume the rational number on the stack.

    numerator denominator [gcd] nullary
------------------------------------------
      numerator denominator divisor

Then we build a little divide-by-divisor program and apply it to the both the numerator and denominator with app2:

   numerator denominator divisor [div] cons app2
---------------------------------------------------
      numerator denominator [divisor div] app2
   ----------------------------------------------
       numerator/divisor denominator/divisor

≡ `reduce-fraction`

[reduce-fraction [gcd] nullary [div] cons app2] inscribe

The Code

Putting it all together, here is the code for the four arithmetic operations. It's presented with the "top most" functions first followed by the supporting functions.

add-frac _add-frac reduce-fraction
sub-frac _sub-frac reduce-fraction
mul-frac _mul-frac reduce-fraction
div-frac _div-frac reduce-fraction

reduce-fraction [gcd] nullary [div] cons app2
gcd true [tuck mod ?] loop pop

_add-frac [_ad+bc] _/bd
_sub-frac [_ad-bc] _/bd
_mul-frac [_ac] _/bd
_div-frac [_ad] [_bc] cleft

_ad+bc _ad_bc add
_ad-bc _ad_bc sub
_ad_bc [_ad] [_bc] fork

_/bd [_bd] cleft

_ac pop popd mul
_ad [popop] dip mul
_bc pop mul popd
_bd popd mul popd

Comparison

cmp-frac [_div-frac] dipdd cmp

eq-frac _div-frac eq
gt-frac _div-frac gt
lt-frac _div-frac lt
neq-frac _div-frac neq
le-frac _div-frac le
ge-frac _div-frac ge