rational arithmetic implementation notes
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 !
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 !
1 post
• Page 1 of 1
rational arithmetic implementation notes
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
, and lines of the sort:
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,
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
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¨ ⍵.
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: 238
- Joined: Thu Jul 28, 2011 10:53 am
1 post
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group