## 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

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 y1`

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

Base Value

`      m1b ← {¯1⊥⍵,[¯0.5]⍺}      (x-y) ≡ x m1b y1`

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 y1`

m1t is substantially slower than m1b.
Roger|Dyalog

Posts: 238
Joined: Thu Jul 28, 2011 10:53 am

### Re: subtraction on 1-byte integers

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