Dumb Spin question

David Betz

Can the || (absolute value) operator ever return a negative number? I'm thinking of the case where the input value is the largest negative number $80000000. If you negate that you get the same value back. Will the || operator do that and return a negative value for that case?

Edit: Maybe it would be good if I describe what I'm trying to do. I want to generate a random number between 0 and n-1 and am trying to do it like this:

  x := ||?seed // n

However, I'm afraid that if ?seed returns $80000000 then I'll get a negative result.

David Betz

Hmmm... Now that I think of it, maybe this would do the trick:

  x := ||(&seed // n)

Mike Green

Yes, || $80000000 would give a result of $80000000. It uses the absolute value instruction which conditionally does a negate based on the sign bit.

mmowen

signed values are represented in two's compliment form hence, the "largest" negative value is actually $8000_0001 (-2147483647) and the largest positive is $7FFF_FFFF (2147483647); the value $8000_0000 is actually a minus ZERO (sign meaningless)

hope this helps

David Betz

mmowen wrote: »

signed values are represented in two's compliment form hence, the "largest" negative value is actually $8000_0001 (-2147483647) and the largest positive is $7FFF_FFFF (2147483647); the value $8000_0000 is actually a minus ZERO (sign meaningless)

hope this helps

Thanks although I thought that minus zero was actually a concept from one's complement notation. Anyway, I thought maybe Spin did something to take care of that case but I guess it doesn't.

Electrodude

Instead of using "||?seed // n", why don't you use "((?seed) & $7FFF_FFFF) // n"? Simply masking out the sign bit will always return a non-negative value.

mmowen wrote: »

signed values are represented in two's compliment form hence, the "largest" negative value is actually $8000_0001 (-2147483647) and the largest positive is $7FFF_FFFF (2147483647); the value $8000_0000 is actually a minus ZERO (sign meaningless)

hope this helps

It's not a minus zero, it's -2147483648. There's no such thing as minus zero in two's complement arithmetic. It isn't adjacent to any numbers remotely near zero. It could be either -2147483648 or 2147483648, since it's adjacent to both -2147483647 and 2147483647, but the standard interpretation is that it is negative because numbers with their top bit set are negative.

I ran the following C program on my computer with no optimization, and it printed out -2147483648 twice:

#include <stdio.h>

int main(int argc, char **argv)
{
        int x = 0x80000000;
        printf("%d\n",  x);
        printf("%d\n", -x);
        return 0;
}

Phil Pilgrim (PhiPi)

As long as n is small w.r.t. the largest positive number, your results using the // operator will be relatively unbiased. Where you get into trouble with larger n is when the ? operator returns a number as large as, or larger than, the largest multiple of n that fits in 31 bits. You can eliminate this bias by determining what that largest multiple is, then throwing out ? results that are at least as large before applying the // operator.

-Phil

David Betz

Electrodude wrote: »

Instead of using "||?seed // n", why don't you use "((?seed) & $7FFF_FFFF) // n"? Simply masking out the sign bit will always return a non-negative value.

Thanks. Yes, that would probably work as well as my second suggestion of using ||(?seed // n).

JonnyMac

I use a variant of Heater's random object and when I want a positive value I tend to do this.

  value := (prng.random >> 1) // SPAN + MIN_VAL

David Betz

JonnyMac wrote: »

I use a variant of Heater's random object and when I want a positive value I tend to do this.

  value := (prng.random >> 1) // SPAN + MIN_VAL

What is the purpose of shifting right by one? Is the low order bit not random?

Dave Hein

Shifting right is another way to get a positive value. It requires fewer bytecodes and may be slightly faster than "& $7fffffff".

David Betz

Dave Hein wrote: »

Shifting right is another way to get a positive value. It requires fewer bytecodes and may be slightly faster than "& $7fffffff".

I thought all values in Spin were signed. Doesn't >> sign extend?

Dave Hein

~> does sign extension. >> inserts zeroes.

David Betz

Dave Hein wrote: »

~> does sign extension. >> inserts zeroes.

You can tell I'm a Spin dunce. Hence the title of this thread. Thanks!

Mark_T

mmowen wrote: »

signed values are represented in two's compliment form hence, the "largest" negative value is actually $8000_0001 (-2147483647) and the largest positive is $7FFF_FFFF (2147483647); the value $8000_0000 is actually a minus ZERO (sign meaningless)

hope this helps

Usually worth checking your facts before posting I find.
Its 2's compl_e_ment, not compl_i_ment and $80000000 _is_ a negative value and is completely meaningful,
but happens to have no representation of its absolute value in 32 bits.
https://en.wikipedia.org/wiki/Two%27s_complement

wmosscrop

Dave Hein wrote: »

Shifting right is another way to get a positive value. It requires fewer bytecodes and may be slightly faster than "& $7fffffff".

I would have thought that the opposite would be true, that the & operation would require fewer bytecodes. Can you explain why?

Thanks,

Walter

kwinn

My guess is that shifting is a single PASM instruction that does not require a second long for the $7fffffff bit mask.

JonnyMac

For fun I ran a timing test. AND-ing takes 704 ticks while shifting right by one takes 656 ticks. The latter is faster by 48 ticks (0.6us).

  seed := ?cnt

  t1 := -cnt
  result := seed & $7FFF_FFFF
  t1 += cnt - 544
  term.dec(t1)
  term.tx(13)

  t1 := -cnt
  result := seed >> 1
  t1 += cnt - 544 
  term.dec(t1)
  term.tx(13)

To be fair, result is different given the same seed. For applications where a random value is desired, this is okay. To have the same result using these techniques the shifting variant would have to be changed to:

  t1 := -cnt
  result := (seed << 1) >> 1
  t1 += cnt - 544 
  term.dec(t1)
  term.tx(13)

...which now takes 992 ticks.

For grins I opened BST to look at the compiled output:

64                        result := seed & $7FFF_FFFF
Addr : 0049:             64  : Variable Operation Local Offset - 1 Read
Addr : 004A:          37 3E  : Constant Mask Y=62 Decrement 7FFFFFFF 2147483647
Addr : 004C:             E8  : Math Op &     
Addr : 004D:             61  : Variable Operation Local Offset - 0 Write

70                        result := seed >> 1
Addr : 0065:             64  : Variable Operation Local Offset - 1 Read
Addr : 0066:             36  : Constant 2 $00000001
Addr : 0067:             E2  : Math Op >>    
Addr : 0068:             61  : Variable Operation Local Offset - 0 Write

Seems like the speed difference from the original comparison is due to an extra hub read.

Electrodude

I love the $37 Constant Mask opcode. It's incredible how many useful constants it can encode in only one data byte.

Anyway, I agree with JonnyMac that "x >> 1" is faster than "x & $7FFF_FFFF" because the constant 1 is only one byte of PNUT ($36: push 1) while $7FFF_FFFF is two ($37 $3E: push constant mask, Y = $3E). I'll bet the >> and & operators themselves take exactly the same amount of cycles to run.

Dave Hein

$7fffffff requires 2 bytes and "1" requires 1 byte. Spin has special bytecodes to represent -1, 0 and 1. Normally, Spin would require 5 bytes to represent a 32-bit value such as $7fffffff, but values of powers of 2 and powers of 2 minus 1 can be represented by a special 2-byte code. $7fffffff is equal to "(1 << 31) - 1", and can be represented by the special 2-byte code. The Spin interpreter requires a few extra cycles to decode a 2-byte constant.

wmosscrop

Thanks for the explanation. I didn't consider the difference in length of the representations of the constants.

mmowen

Electrodude wrote: »

Instead of using "||?seed // n", why don't you use "((?seed) & $7FFF_FFFF) // n"? Simply masking out the sign bit will always return a non-negative value.

mmowen wrote: »

signed values are represented in two's compliment form hence, the "largest" negative value is actually $8000_0001 (-2147483647) and the largest positive is $7FFF_FFFF (2147483647); the value $8000_0000 is actually a minus ZERO (sign meaningless)

hope this helps

It's not a minus zero, it's -2147483648. There's no such thing as minus zero in two's complement arithmetic. It isn't adjacent to any numbers remotely near zero. It could be either -2147483648 or 2147483648, since it's adjacent to both -2147483647 and 2147483647, but the standard interpretation is that it is negative because numbers with their top bit set are negative.

I ran the following C program on my computer with no optimization, and it printed out -2147483648 twice:

#include <stdio.h>

int main(int argc, char **argv)
{
        int x = 0x80000000;
        printf("%d\n",  x);
        printf("%d\n", -x);
        return 0;
}

Try this then just for grins:

CON 
  _clkmode = xtal1 + pll16x                  ' System clock → 80 MHz
  _xinfreq = 5_000_000                       ' external crystal 5MHz

OBJ
  PST   : "Parallax Serial Terminal"
  SN    : "Simple_Numbers"

PUB Main | value

  PST.Start(115_200)

  repeat 3
    waitcnt(clkfreq+cnt)

  value := -2147483647 '$8000_0001
  PST.Str(SN.hex(value,8))
  PST.NewLine
  PST.Str(SN.dec(value))
  PST.NewLine
  
  PST.Str(SN.hex(||value,8))
  PST.NewLine
  PST.Str(SN.dec(||value))
  PST.NewLine

  value := 2147483648 '$8000_000
  PST.Str(SN.hex(value,8))
  PST.NewLine
  PST.Str(SN.dec(value))
  PST.NewLine
  
  PST.Str(SN.hex(||value,8))
  PST.NewLine
  PST.Str(SN.dec(||value))
  PST.NewLine

I get the following as a a result:
80000001
-2147483647
7FFFFFFF
2147483647
80000000
-0
80000000
-0

Electrodude

Congratulations, you found a bug in Simple_Numbers.spin! If you look at the source of Simple_Numbers.decstr, you'll see that it first checks if the number is negative, and, if it is, it outputs a "-", negates the number, and continues. There is no special case, like there technically should be due to the fact that -$8000_0000 == $8000_0000. I'm sure at least one of the two very smart authors of that object was aware of the problem but ignored it because he preferred not to add a special case to fix a problem that would almost never happen.

JonnyMac

The .dec() method in FullDuplexSerial accounts for NEGX.

ChrisGadd

Ensuring that the number is positive is just part of the problem; David also wants to limit it to a range of 0 to n-1. Once you include the // n operator, it seems that the initial solution is fastest.
The actual amount of time varies depending on what n is, but typically:
||(seed // n) executes in ~1408
seed >> 1 // n executes in ~1568
seed & $7FFF_FFFF // n executes in ~1616

Electrodude

That makes sense, since >> 1 takes two bytes (push constant 1, shift right) while || takes only one (abs).