Need a couple math routines

Oldbitcollector (Jeff) · 2010-02-11 14:41

I've started using byte increments for calculating time in my game loops.
This works, but it would be handy to be able to perform functions based on timing.

Can someone help with a couple routines for determining if the byte is:

* an even number. (true/false)
* divisible by 5. (true/false)

Thanks
OBC

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?

Visit the: The Propeller Pages @ Warranty Void.

Mike Green · 2010-02-11 15:05

Even number? Just test bit 0.

IF Value & 1 ' succeeds if odd
IFNOT Value & 1 ' succeeds if even

or

TEST Value,#1 wz ' zero true if even
TEST Value,#1 wc ' carry true if odd

Post Edited (Mike Green) : 2/11/2010 3:10:27 PM GMT

Mike Green · 2010-02-11 15:09

Divisible by 5 is harder. What's the range of values involved? Spin or Assembly?

Oldbitcollector (Jeff) · 2010-02-11 15:14

@Mike

Range is 0 - 254 in spin.

OBC

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?

Visit the: The Propeller Pages @ Warranty Void.

jazzed · 2010-02-11 15:17

Use this for general purpose PASM: forums.parallax.com/forums/default.aspx?f=25&m=372927
Note this line at bottom of code on OP: 'Reamainder is what left in arg1

Spin is easy: ifnot number // 5 ' if true number is evenly divisible

Here's an interesting link: mathforum.org/dr.math/faq/faq.divisibility.html

Post Edited (jazzed) : 2/11/2010 5:15:32 PM GMT

Oldbitcollector (Jeff) · 2010-02-11 15:22

Mike Green said...
Even number? Just test bit 0.

IF Value & 1 ' succeeds if odd
IFNOT Value & 1 ' succeeds if even

Duh.. (head smack) My brain seems to default to decimal numbering. So a test routine might look like..

PRI CheckEven (timer) | even
    
    even := false

    IFNOT timer & 1
       even := true
   
    return timer

OBC

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?

Visit the: The Propeller Pages @ Warranty Void.

Mike Green · 2010-02-11 15:38

You could simplify this even more with:

PRI Even(thing)
   return (thing & 1) == 0

mpark · 2010-02-11 15:55

jazzed said...

Edit: if it's just to test divisible by 5:

and number,#7
cmp number,#5 wz
if_nz test number,#0 wz

Here's an interesting link: mathforum.org/dr.math/faq/faq.divisibility.html

That "last digit is 5 or 0" test only works in decimal! Your code fails if number is 10, e.g.

Cluso99 · 2010-02-11 15:56

OBC: The counters are a good way for timing independent code. I recently started to play with them in pasm.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Links to other interesting threads:

· Home of the MultiBladeProps: TriBlade,·RamBlade,·SixBlade, website
· Single Board Computer:·3 Propeller ICs·and a·TriBladeProp board (ZiCog Z80 Emulator)
· Prop Tools under Development or Completed (Index)
· Emulators: CPUs Z80 etc; Micros Altair etc;· Terminals·VT100 etc; (Index) ZiCog (Z80) , MoCog (6809)·
· Prop OS: SphinxOS·, PropDos , PropCmd··· Search the Propeller forums·(uses advanced Google search)
My cruising website is: ·www.bluemagic.biz·· MultiBlade Props: www.cluso.bluemagic.biz

jazzed · 2010-02-11 17:12

mpark said...

jazzed said...

Yuck snipped! [noparse]:)[/noparse]

That "last digit is 5 or 0" test only works in decimal! Your code fails if number is 10, e.g.

You're right. I was half asleep [noparse]:)[/noparse]

JonnyMac · 2010-02-11 19:08

The divide by 5 shouldn't be hard -- what about this?:

pub divideby5(value)

  return ((value // 5) == 0)

[noparse][[/noparse]Edit] -- I just saw that [noparse][[/noparse]another version of] this solution was previously posted.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon McPhalen
Hollywood, CA

Post Edited (JonnyMac) : 2/11/2010 7:14:24 PM GMT

Bocephus · 2010-02-11 19:51

If multiplication is faster than division in Spin?

  _clkmode      = xtal1 + pll16x                     
  _xinfreq      = 5_000_000
  
OBJ
  tv : "tv_text"                                                                        

PUB main | number, div_five
  number := 145
  div_five := $CCCD
  
  tv.start(13)
  tv.dec(number)  
  tv.str(string(" divided by five = "))
  
  number := (number * div_five) >> 18 
  tv.dec(number)

Mike Green · 2010-02-11 20:02

Multiplication in Spin is slightly faster than division. The overhead of fetching and decoding the byte codes would tend to mask any differences as well as pushes and pops needed. It would be easy enough to do the operation 10000 times and time it using the system clock, then repeating the same loop with the other operation and comparing the results.

VIRAND · 2010-02-11 21:21

Magickalogickal Method:

if (num8bits * $33) & $FF == 0 'if a number under 256 is divisible by 5 ...

or

if (num16bits * $3333) & $FFFF == 0 'if a number under 65536 is divisible by 5 ...

In assembly, this is done on LONGS with 16 shifts and 16 adds, and the result long = 0 if it divides 5 with zero remainder.
(or just one MUL, if we had one)

I am not sure whether this trick works with Spin variables defined as bytes or words, because it is an overflow trick.

I also don't know if it has any advantage over // if the remainder is re-normalized by a division by the "hex 3" nybbles.

This may fail on the number 5. If so, I would try fixing it by adding one to the variable being tested product.
I haven't actually tried it, so it may not work at all.

Bocephus method seems like a similar concept.

Post Edited (VIRAND) : 2/11/2010 10:02:37 PM GMT

Bocephus · 2010-02-11 21:37

@Mike Green: You are right. I timed the two and I was surprised to see mine is slower.

Oldbitcollector (Jeff) · 2010-02-12 00:42

'Thank ya, gang!

OBC

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?

Visit the: The Propeller Pages @ Warranty Void.

CannibalRobotics · 2010-02-12 02:03

Little late to the party here but isn't anything multiplied by 2 ending in 0 divisible by 5? - if so then it's one bit shift to the left and test for dec 0?
jim

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Signature space for rent!
Send $1 to CannibalRobotics.com.

tonyp12 · 2010-02-12 02:47

As you are only dealing with 49 possible numbers (0-254), you could have a look-up table of these 49

But I did a check for the last 4 bits and the pattern repeat after 16.
so binary-and the number with %1111
check if result is any of the 16 below.
Is 0/5·valid?, if not check if start value <>0 as 80 have·same 4 bits as zero

0101 5
1010 10
1111 15
0100 20
1001 25
1110 30
0011 35
1000 40
1101 45
0010 50
0111 55
1100 60
0001 65
0110 70
1011 75
0000 80

0101 85 < repeat
1010 90
1111 95
0100 100
1001 105
1110 110
0011 115
1000 120

Post Edited (tonyp12) : 2/12/2010 3:05:48 AM GMT

tonyp12 · 2010-02-12 03:11

Is a see a repeat pattern in 8 with 3 bits
and 4 only possible with 2 bits
could be so simple as: if(number and%11)== 0 || 5 || 10 || 15

00 0
01 5
10 10
11 15

00 20
01 25
10 30
11 35

00 40
01 45
10 50
11 55

00 60
01 65
10 70
11 75

Dave Hein · 2010-02-12 03:14

If you have the memory available just do a 255-byte lookup table.· It's probably the fastest way to do it in Spin.

VIRAND · 2010-02-12 13:26

You'd only need a 8 long lookup table then... 8x4=32bytesx 8bits=256 (including 0)
There are 51 multiples of 5 between and including 0 and 255.

There must be a solution involving the 2 lowest bits but I didn't think of that.

Obviously the lookup table is going to be
%100001000010000............................1000010000100001
and is probably pointless to lookup when num//5==0 is available.
Both bit and byte lookup tables waste memory and one wastes time except in PASM.

CannibalRobotics · 2010-02-12 14:50

@tonyp12
Problem with the two lowest bits is that they are not exclusive.
05 => #0101 for last two bits also 1, 9, 13
10 => #1010 for last two bits also 2, 6, 14
15 => #1111 for last two bits also 3, 7, 11

@Virand
There are only 25 multiples of 10, 4 multiples of 50 and so on. What if you multiplied by 2 then chopped the number down the number to 3 bits. If it's a multiple of 5 then those are 000.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Signature space for rent!
Send $1 to CannibalRobotics.com.

mpark · 2010-02-12 19:16

How do you propose to chop the number to 3 bits? Bitwise-anding %111 won't work. Suppose your original number is 4. Multiply it by 2 to get 8. The last three bits are %000 but 4 is not a multiple of 5.

kwinn · 2010-02-12 20:25

Simplest is probably a modified binary search. The multiple if statements could be replaced by a loop and a 6 byte array.

if no > 130 no = no - 130
if no = 0 then multiple of 5
if no > 65 no = no - 65
if no = 0 then multiple of 5
if no > 35 no = no - 35
if no = 0 then multiple of 5
if no > 20 no = no - 20
if no = 0 then multiple of 5
if no > 10 no = no - 10
if no = 0 then multiple of 5
if no > 5 no = no - 5
if no = 0 then multiple of 5

Need a couple math routines

Comments