subtraction on 1-byte integers

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 !

subtraction on 1-byte integers

Postby Roger|Dyalog on Fri Jun 04, 2021 1:02 am

In a previous post, Addition on 1-Byte Integers, the game was to write a function g such that

      (x+y) ≡ x g y

for x and y of interest where g does not use + or -. Here, the game is to write a function g which does not use + or -, so that for 1-byte integer vectors x and y:

      all1 ← {¯128,(⍎∊(⊂' ¯'),¨⍕¨⌽1↓a),a←⍳128}  ⍝ all 1-byte ints
A ← all1 ⍬

x ← A[?5678 ⍴ ≢A]
y ← A[?5678 ⍴ ≢A]

(x-y) ≡ x h y
1

⎕io←0 is assumed. ⎕io delenda est!

Base Value

      m1b ← {¯1⊥⍵,[¯0.5]⍺}

(x-y) ≡ x m1b y
1

From the definition of ⍺⊥⍵ it can be shown that ¯1⊥⍵,⍺ ←→ ⍺-⍵ and more generally ¯1⊥⍺,[¯0.5]⍵ ←→ ⍺-⍵.

Table Look-Up

      minusT ← {⊖ 256 256 ↑ 256 512 ⍴ (⌽a),⍎∊(⊂' ¯'),¨⍕¨1↓a←⍳256}
⍝ subtraction table for 1-byte ints
A ← all1 ⍬
T ← minus1T ⍬

m1t ← {T[(A⍳⍺),¨(A⍳⍵)]}

(x-y) ≡ x m1t y
1

m1t is substantially slower than m1b.
Roger|Dyalog
 
Posts: 236
Joined: Thu Jul 28, 2011 10:53 am

Re: subtraction on 1-byte integers

Postby petermsiegel on Mon Jun 14, 2021 6:01 am

Just for fun, an explicit binary subtraction algorithm!
      Sub←{
⍝ * For each scalar pair of 8-bit integers, ⍺, ⍵,
⍝ calculate ⍺ Sub ⍵ by treating as boolean vectors, using xor (≠) and carries.
⍝ * A slow, but entertaining, algorithm
⍝ * While ⍺, ⍵ are required to be ≤8-bits, the result may be 9-bits
⍝ (allowed per the problem stmt)

83≠⎕DR ⍺,⍵,2:⎕SIGNAL 11 ⍝ ⍺, ⍵: 8-bit ints only (,2: handle ⍺,⍵ boolean)

BitsOut←(9⍴2)∘⊤ ⍝ 1st bit is sign bit. Be prepared for 9 bits
BitsIn←2∘⊥{⊃⍵:¯1,⍵ ⋄ ⍵} ⍝ signed decode
ShiftL1←(0,⍨1∘↓) ⍝ shift boolean vector 1 to left
⍝ SubB: Boolean subtract using boolean xor and carry...
⍝ APL PSEUDO-CODE
⍝ ¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯
⍝ SubB←{ ⍝ Calculate a-w
⍝ 1(~∊)⍵:⍺ ⍝ while (w != 0)
⍝ c←(~⍺)∧⍵ ⍝ carry = (~a) & w;
⍝ a←⍺≠⍵ ⍝ a = a ^ w;
⍝ w←ShiftL1 c ⍝ w = carry << 1;
⍝ a ∇ w ⍝ continue
⍝ } ⍝ return a
SubB←{1(~∊)⍵:⍺ ⋄ (⍺≠⍵)∇ ShiftL1 ⍵∧~⍺}

⍝ Sub is a scalar fn..
⍺{BitsIn(BitsOut ⍺)SubB BitsOut ⍵}¨⍵
}

And it's blazingly slow!
      cmpx 'x m1b y' 'x Sub y' 'x m1t y'
x m1b y → 7.8E¯6 | 0%
x Sub y → 2.6E¯2 | +327100% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
x m1t y → 7.6E¯4 | +9600% ⎕
petermsiegel
 
Posts: 98
Joined: Thu Nov 11, 2010 11:04 pm


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest