encode

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 !

encode

Postby Roger|Dyalog on Sat Aug 15, 2020 8:34 pm

Encode, the dyadic function ⍺⊤⍵, in its “kernel”, expresses scalar ⍵ in the base of vector ⍺. For example,

      24 60 60 ⊤ 7654
2 7 34
2 2 2 2⊤11
1 0 1 1

computes that there are 2 hours, 7 minutes, and 34 seconds in 7654 seconds and that 11 in binary is 1 0 1 1.

Model

      
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}

z←x encode y;⎕ct;i
⍝ x⊤y
assert(1=≢⍴x)∧0=≢⍴y
⎕ct←0
z←0⍴y
:For i :In ⌽⍳≢x
z←(x[i]|y),z
y←⌊y÷x[i]
:EndFor

For example:

      24 60 60 encode ¯7654
21 52 26
24 60 60 ⊤ ¯7654
21 52 26

Scalar Left Argument

When the left argument is a scalar, ⍺⊤⍵ just does {⎕ct←0 ⋄ ⍺|⍵}, that is, a non-tolerant version of ⍺|⍵.

Arthur Whitney suggested a more useful alternative definition, to wit: ⍺⊥⍣¯1⊢⍵, expressing ⍵ in base ⍺ with the scalar ⍺ repeated as many times as necessary. For example:

      encodeS←{⍺⊥⍣¯1⊢⍵}

10 encodeS 1234
1 2 3 4
10 encodeS 123456
1 2 3 4 5 6

2 encodeS 250
1 1 1 1 1 0 1 0
2 ⊥ 1 1 1 1 1 0 1 0
250

Unfortunately, this alternative definition is not backward compatible (however unlikely that existing code is using a scalar left argument in ⊤).

Monadic Encode

⊤ does not have a monadic definition. One possibility is ⊤⍵ ↔ 2⊤⍵, that is, bits or binary representation. (Similarly, ⊥⍵ would be 2⊥⍵, binary value.) This is in fact the definition used in A Formal Description of SYSTEM/360 [Falkoff, Iverson, and Sussenguth 1964, Table 1]. It was actually implemented in APL\360 for a time but was later removed due to space limitations [Hui 1992].

Floating Point vs. Rational

The comparisons implicit in the definition of ⊤ are exact, as if ⎕ct is 0, independent of the setting of ⎕ct. The model reflects this fact. The two places where it matters are in | (residue) and ⌊ (floor).

Exact comparisons coupled with floating-point (FP) numbers make ⊤ not a very good function. The following examples illustrate the point:

      200 0.07⊤7
99 0.07
200 0.07 encode 7
99 0.07

99 0.07 - 200 0.07 ⊤ 7
0 6.10623E¯16

The 0.07 in the result is unexpected (and undesirable) because ostensibly 0.07 divides evenly into 7 and so that element the result should be 0. (APL old-timers may remember the number 0.07, notorious for its inexact FP representation.) The subtraction shows that the number displayed as 0.07 in the result is slightly less than 0.07 and so is a legitimate remainder, but that is small consolation.

The unexpected results can show up in unexpected places, for ordinary-looking numbers:

      1.1 2.1 ⊤ 70
1.1 0.7
1.1 2.1 ⊤ 71
1.1 1.7

The function can be improved somewhat by using tolerant comparisons in the definition, modeled as follows:

      
z←x encodeT y;i
⍝ x⊤y using tolerant comparisons
assert(1=≢⍴x)∧0=≢⍴y
z←0⍴y
:For i :In ⌽⍳≢x
z←(x[i]|y),z
y←⌊y÷x[i]
:EndFor

⎕ct
1E¯14
200 0.07 encodeT 7
100 0
1.1 2.1 encodeT 70
0 0.7
1.1 2.1 encodeT 71
0 1.7

But there are still tiny (epsilon-sized) flaws:

      1.1 2.1 encodeT 3
1 0.9
1 0.9 - 1.1 2.1 encodeT 3
0 1.11022E¯16

The function can be “rescued” by using rational numbers. To compute with rationals, in the model function convert each function f which is not a selection or structural function to f Q , and use qi to convert ordinary numbers to rational numbers. (Q and qi are from Rational Arithmetic.)

      
z←x qencode y;i
⍝ x⊤y on rationals
assert(1=≢⍴x)∧0=≢⍴y
z←0⍴y
:For i :In ⌽⍳≢x
z←(x[i] |Q y),z
y←⌊Q y ÷Q x[i]
:EndFor

qi 200 0.07
┌───────────┬───────────┐
│┌─────┬─┬─┐│┌─┬─────┬─┐│
││2 0 0│1│1│││7│1 0 0│1││
│└─────┴─┴─┘│└─┴─────┴─┘│
└───────────┴───────────┘
qi 7
┌───────┐
│┌─┬─┬─┐│
││7│1│1││
│└─┴─┴─┘│
└───────┘
(qi 200 0.07) qencode qi 7
┌───────────┬───────┐
│┌─────┬─┬─┐│┌─┬─┬─┐│
││1 0 0│1│1│││0│1│0││
│└─────┴─┴─┘│└─┴─┴─┘│
└───────────┴───────┘
⍕Q (qi 200 0.07) qencode qi 7
100 0

A rational number is an enclosed triplet of the decimal digits of the numerator, the decimal digits of the denominator, and a sign (¯1, 0, or 1).

qencode on the other problematic examples:

      (qi 1.1 2.1) qencode⍤1 0⊢ qi 3 70 71
┌───────┬───────────┐
│┌─┬─┬─┐│┌─┬───┬─┐ │
││1│1│1│││9│1 0│1│ │
│└─┴─┴─┘│└─┴───┴─┘ │
├───────┼───────────┤
│┌─┬─┬─┐│┌─┬───┬─┐ │
││0│1│0│││7│1 0│1│ │
│└─┴─┴─┘│└─┴───┴─┘ │
├───────┼───────────┤
│┌─┬─┬─┐│┌───┬───┬─┐│
││0│1│0│││1 7│1 0│1││
│└─┴─┴─┘│└───┴───┴─┘│
└───────┴───────────┘
⍕Q (qi 1.1 2.1) qencode⍤1 0⊢ qi 3 70 71
1 9r10
0 7r10
0 17r10
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