## subtraction on 1-byte integers

**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 !

2 posts
• Page

**1**of**1**### subtraction on 1-byte integers

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

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:

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

Base Value

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

Table Look-Up

m1t is substantially slower than m1b.

(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

Just for fun, an explicit binary subtraction algorithm!

And it's blazingly slow!

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

2 posts
• 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