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 !
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: 238
- 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: 146
- Joined: Thu Nov 11, 2010 11:04 pm
2 posts
• Page 1 of 1
Who is online
Users browsing this forum: ray and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group