rational arithmetic implementation notes

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

rational arithmetic implementation notes

Postby Roger|Dyalog on Tue Jul 14, 2020 1:33 am

A monadic operator Q is presented in the APL Chat Forum post Rational Arithmetic. Here, we present some notes on its implementation.

Organization

Q has a series of definitions of “i functions” and “q functions” (more about them later), and

      f ← (⍺⍺{aa←⍺⍺ ⋄ ⊃⎕CR'aa'}⍵),1+0≠⎕NC'⍺'
e←¯3=≡⍵

, and lines of the sort:

      e∧'÷' 1≡f:qrecip ⍵
e<'÷' 2≡f:⍺ qdiv ⍵
e∧'÷' 2≡f:⍺ qdiv¨⍵

f is a 2-element vector (a) of the character representation of the operand function ⍺⍺ and (b) of the valence of the invoked derived function, 1 if monadic or 2 if dyadic. (Ideally, the first part of f can be simpler but currently ⎕cr'⍺⍺' is disallowed. One can hope that the above circumlocution will be unnecessary before too long.) e is a boolean scalar, 1 if ⍵ is a rational scalar and 0 if it is a disclosed scalar. (⍵ would be disclosed in f Q/⍵.) Therefore, each guarded line checks for a case and invokes the appropriate function. In the lines above,

  • e∧'÷' 1≡f checks for ÷Q ⍵ an invokes qrecip¨ ⍵;
  • e<'÷' 2≡f checks for ÷Q/⍵ and invokes ⍺ qdiv ⍵; and
  • e∧'÷' 2≡f checks for ⍺ ÷Q ⍵ and invokes ⍺ qdiv¨ ⍵.
See the APL Chat Forum post A Design Exercise for a discussion of the f Q versus f Q/ issue.

The i Functions

The “i functions” perform some key computations on vectors of decimal digits representing extended precision integers. Chief among them is itimes, which does multiplication using FFT [Hui 2016, §32; dfns xtimes], and idiv, which computes the integer quotient (⌊⍺÷⍵) on vectors of decimal digits, defined using ÷nats from the dfns workspace [dfns nats].

The q Functions

The “q functions” mostly implement particular cases of ⍺⍺ Q, typically one function for the monadic case and another for the dyadic case. (For example, qrecip for ÷Q ⍵ and qdiv for ⍺ ÷Q ⍵.) The scalar q functions apply to individual disclosed rational numbers (the numerator,denominator,sign triplets) and return a disclosed rational number result.

Non-scalar q functions (currently ⌹Q, ⍕Q, and ⊤Q) apply to rational array arguments and return an array result.

Boolean Functions

The rational comparison functions <Q, ≤Q, etc. are based on the ⍺ qcmp ⍵ function, which returns ¯1, 0, or 1 depending on whether ⍺ less than, equal to, or greater than ⍵. Comparisons of rational numbers are exact, as if ⎕ct is 0 (no matter what the current setting of ⎕ct is).

*

Rational ⍺*⍵ requires that ⍵ be an integer. (The requirement may be relaxed in the future for ⍺ which is a perfect root.) ⍵ is further assumed to be < 1e15 (unless ⍺ is 0 or 1 or ¯1) because for the forseeable future a larger ⍵ would engender a result with a number of digits that would cause a WS FULL.

The ⍺*⍵ result obtains by repeated squaring.



Implementing ⌹ on rational numbers is straightforward because there are no errors with floating point representation and computation. Simple Gaussian elimination is used and in the process, if a 0-column is encountered, then the matrix is singular, no ifs and buts and questions of whether a number “is really zero”.



⍕⍵ formats a rational array. A rational number is formatted in the form numerator followed by the letter r followed by the denominator, but if the denominator is 1 then the trailing “r1” is elided. The columns of individually formatted numbers are right-aligned.

In ⍺⍕⍵, ⍺ is a scalar integer. ⍺≥0 specifies fixed-point format with ⍺ digits after the decimal point. ⍺<0 specifies exponential format with |⍺ significant digits. The implementation of these was ... amusing. Exponential format, especially the exponent, is straightforward if you stick to first principles, to the mathematics: 10⍟a×b ↔ (10⍟a)+10⍟b; 10⍟a×10*k ↔ (10⍟a)+k; etc.); 10⊥a,k⍴0 ↔ (10⊥a)×10*k; 10⊥(k+≢a)↑a ↔ (10⊥a)×10*k (assuming that ⍟ and + and ⊥ and × and * had extended precision).

For ⍺⍕⍵, columns of individually formatted numbers are aligned on the decimal point (and also on the “e” for exponential format).

created:_2020-07-13
updated: 2020-08-14
Roger|Dyalog
 
Posts: 207
Joined: Thu Jul 28, 2011 10:53 am

Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest