Simulating int arithmetic with wrap-around

[Steve D'Aprano]

It's easy to simulate integer arithmetic with wrap-around for *unsigned*
ints. For example, imagine a four-bit integer (0 through 15):

# Addition
py> (7 + 8) & 0xF
15
py> (7 + 9) & 0xF
0
py> (7 + 10) & 0xF
1

# Multiplication
py> (7 * 2) & 0xF
14
py> (7 * 3) & 0xF
5
py> (7 * 4) & 0xF
12


And in general, for any operator ⊗, and a and b both in the range 0 through
2**N-1, we can simulate unsigned N-bit integer arithmetic with:

a⊗b & (2**N - 1)

(I think this works for all the arithmetic operators, and the bitwise
operations. The bitmask & 2**N-1 is not needed for the bitwise operations
except for left-shift.)


How about *signed* integers?

7 + 1 => -8
7 + 2 => -7
7 + 7 => -2

7 * 2 => -2
7 * 3 => 5
7 * 4 => -4


Again, assume both operands are in range for an N-bit signed integer. What's
a good way to efficiently, or at least not too inefficiently, do the
calculations in Python?


Signed arithmetic also has some gotchas. For example, -x is not necessarily
defined, nor is abs(x).


Thanks,





--
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

[Serhiy Storchaka]

On 30.12.16 16:47, Steve D'Aprano wrote:
> Again, assume both operands are in range for an N-bit signed integer. What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

def to_unsigned(bits, x):
return x & ((1<<bits)-1)

def to_signed(bits, x):
offset = 1<<(bits-1)
return to_unsigned(bits, x + offset) - offset

[Chris Angelico]

On Sat, Dec 31, 2016 at 1:47 AM, Steve D'Aprano
<steve+...@pearwood.info> wrote:
> How about *signed* integers?
>
> 7 + 1 => -8
> 7 + 2 => -7
> 7 + 7 => -2
>
> 7 * 2 => -2
> 7 * 3 => 5
> 7 * 4 => -4
>
>
> Again, assume both operands are in range for an N-bit signed integer. What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

One way would be to work with the integers as unsigned numbers, and
then render them signed for display only. The neat thing about two's
complement (as opposed to two's compliment, which is a really sweet
thing to say to someone) is that a lot of operations work exactly the
same way. You add 7+2 and get 9, and then display 9 as -7. You take
that 9 (really -7) and add 5 to it, and you get 14, which you display
as -2. Add another 4 and you get 18, mask that off and you get 2. You
may have to handle multiplication and division differently, I think,
and you might need a sign-extend right shift operator (as opposed to a
zero-fill right shift), but they should be able to be defined in terms
of the other operations.

7 * 2 => 14, displayed as -2
7 * 3 => 21, mask to 5
7 * 4 => 28, mask to 12, display as -4
7 * 9 => 63, mask to 15, display as -1. Conceptually 7*-7 => -49.

Actually you might be able to get away with multiplication perfectly.
I'm thinking of the Intel 80x86 opcodes, where MUL and IMUL are
unsigned and signed multiplication, respectively, but they differ
because the result is twice as wide as the operands (eg if you
multiply two 16-bit numbers, you get a 32-bit result). The Intel chips
do the same with division (eg you divide a 32-bit number by a 16-bit
and get back a 16-bit quotient and 16-bit remainder). You may be able
to take the exact same short-cut.

> Signed arithmetic also has some gotchas. For example, -x is not necessarily
> defined, nor is abs(x).

AIUI -x is always defined, but might be equal to x in two
circumstances (zero and MAXINT+1). Not sure about abs(x), but probably
would be the same.

ChrisA

[Steve D'Aprano]

Thanks.

Are you saying that the best way of doing this is this?

(1) convert signed Python ints to unsigned;

(2) perform operation and bitmask;

(3) convert unsigned back to signed.


Here's an example. I want to multiply 7*3 using a signed 4-bit int, getting
5 as the answer, and 7*4 getting -4 as the answer:


py> N = 4
py> to_signed(N, to_unsigned(N, 7) * to_unsigned(N, 3) & (2**N - 1))
5
py> to_signed(N, to_unsigned(N, 7) * to_unsigned(N, 4) & (2**N - 1))
-4



It works, but I'm glad I won't be doing anything that requires great
speed :-)

[Serhiy Storchaka]

On 31.12.16 02:30, Steve D'Aprano wrote:
> Are you saying that the best way of doing this is this?
>
> (1) convert signed Python ints to unsigned;
>
> (2) perform operation and bitmask;
>
> (3) convert unsigned back to signed.
>
>
> Here's an example. I want to multiply 7*3 using a signed 4-bit int, getting
> 5 as the answer, and 7*4 getting -4 as the answer:
>
>
> py> N = 4
> py> to_signed(N, to_unsigned(N, 7) * to_unsigned(N, 3) & (2**N - 1))
> 5
> py> to_signed(N, to_unsigned(N, 7) * to_unsigned(N, 4) & (2**N - 1))
> -4

Step 1 is not needed. And you can inline to_unsigned() in to_signed(). I
introduced it just for clearness.

py> to_signed(N, 7 * 3)
5
py> to_signed(N, 7 * 4)
-4

[Paul Rubin]

Steve D'Aprano <steve+...@pearwood.info> writes:
> Again, assume both operands are in range for an N-bit signed integer. What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

My first thought is towards the struct module, especially if you want to
handle a bunch of such integers at the same time. Or maybe the array
module or some combination. Or a C extension.

[Gregory Ewing]

Paul Rubin wrote:
> My first thought is towards the struct module, especially if you want to
> handle a bunch of such integers at the same time. Or maybe the array
> module or some combination.

Or possibly numpy.

--
Greg

[Random832]

On Fri, Dec 30, 2016, at 09:47, Steve D'Aprano wrote:
> Again, assume both operands are in range for an N-bit signed integer.
> What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

I'd do something like:

bit_mask = (1 << bits) - 1 # 0xFFFF
sign_bit = 1 << (bits - 1) # 0x8000
sign_ext = ~bit_mask # ...FFFFF0000

def signed(value):
if value & sign_bit:
return value | sign_ext
else:
return value & bit_mask

def unsigned(value):
return value & bit_mask

And also avoid doing it on intermediate steps where it can be shown to
not affect the result or allow the value to grow too large.

[Rob Gaddi]

Agreed. If you had to do a lot of calculations on arbitrary sized
signed/unsigned ints, figuring how to parallelize them into numpy arrays
would save you a ton of time.

--
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order. See above to fix.

[Paul Rubin]

Steve D'Aprano <steve+...@pearwood.info> writes:

> Again, assume both operands are in range for an N-bit signed integer. What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

My first thought is towards the struct module, especially if you want to handle
a bunch of such integers at the same time. Or maybe the array module or some

combination. Or a C extension.

[Rob Gaddi]

On 01/03/2017 10:00 PM, Gregory Ewing wrote:
> Paul Rubin wrote:

>> My first thought is towards the struct module, especially if you want to
>> handle a bunch of such integers at the same time. Or maybe the array
>> module or some combination.
>

[Gregory Ewing]

Paul Rubin wrote:
> My first thought is towards the struct module, especially if you want to
> handle a bunch of such integers at the same time. Or maybe the array
> module or some combination.

Or possibly numpy.

--
Greg

[Random832]

On Fri, Dec 30, 2016, at 09:47, Steve D'Aprano wrote:

> Again, assume both operands are in range for an N-bit signed integer.
> What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?