Shop OBEX P1 Docs P2 Docs Learn Events
Collatz: Uses conditional JMP within REP block — Parallax Forums

Collatz: Uses conditional JMP within REP block

tomcrawfordtomcrawford Posts: 1,129
in Propeller 2
Here is a link to the wikipedia article about the Collatz conjecture in case anybody needs a refresher. And here is link to a forum thread where we pretty much beat it to death.

So here is prop2 code that does a very simple single precision implementation. 
rep   @.mumble, #0       'repeat the following until it gets to one

         cmp   current, #1 wcz    'did it get to one?
   if_E  jmp   #gotToOne          'okay, display and continue
         drvnot  #scope2
         test  current, #1 wcz    'even or odd
   if_Z  shr   current, #1        'divide by two if even
   if_NZ mov   temp, current      'multiply by three if odd
   if_NZ add   current, temp
   if_NZ add   current, temp
   if_NZ add   current, #1        'and add one if odd
         add   count, #1          'increment count
         cmp   current, extent wcz   'largest current for this trial
   if_GT mov   extent, current
.mumble
This is interesting only because I used a REP block that includes a conditional JMP to break out of the REP, when the current number gets to 1.

Comments

  • TonyB_TonyB_ Posts: 2,220
    tomcrawford wrote: »
    Here is a link to the wikipedia article about the Collatz conjecture in case anybody needs a refresher. And here is link to a forum thread where we pretty much beat it to death.

    So here is prop2 code that does a very simple single precision implementation. 
    rep   @.mumble, #0       'repeat the following until it gets to one

         cmp   current, #1 wcz    'did it get to one?
   if_E  jmp   #gotToOne          'okay, display and continue
         drvnot  #scope2
         test  current, #1 wcz    'even or odd
   if_Z  shr   current, #1        'divide by two if even
   if_NZ mov   temp, current      'multiply by three if odd
   if_NZ add   current, temp
   if_NZ add   current, temp
   if_NZ add   current, #1        'and add one if odd
         add   count, #1          'increment count
         cmp   current, extent wcz   'largest current for this trial
   if_GT mov   extent, current
.mumble
    This is interesting only because I used a REP block that includes a conditional JMP to break out of the REP, when the current number gets to 1.

    To me, this is interesting only because the code can be smaller and faster :)
    	rep	@.mumble, #0		'repeat the following until it gets to one

	cmp	current, #1	wz	'did it get to one?
  if_E	jmp	#gotToOne          	'okay, display and continue
	drvnot	#scope2
	testb	current, #0	wc	'even or odd
  if_nc	shr	current, #1        	'divide by two if even
  if_c	mov	temp, current      	'multiply by three and add one if odd
  if_c	add	current, temp
  if_c	addx	current, temp
	add	count, #1          	'increment count
	fge	extent, current
.mumble
  • ElectrodudeElectrodude Posts: 1,682
    edited 2019-01-28 22:52
    TonyB_ wrote: »
    tomcrawford wrote: »
    Here is a link to the wikipedia article about the Collatz conjecture in case anybody needs a refresher. And here is link to a forum thread where we pretty much beat it to death.

    So here is prop2 code that does a very simple single precision implementation. 
    rep   @.mumble, #0       'repeat the following until it gets to one

         cmp   current, #1 wcz    'did it get to one?
   if_E  jmp   #gotToOne          'okay, display and continue
         drvnot  #scope2
         test  current, #1 wcz    'even or odd
   if_Z  shr   current, #1        'divide by two if even
   if_NZ mov   temp, current      'multiply by three if odd
   if_NZ add   current, temp
   if_NZ add   current, temp
   if_NZ add   current, #1        'and add one if odd
         add  count, #1          'increment count
         cmp   current, extent wcz   'largest current for this trial
   if_GT mov   extent, current
.mumble
    This is interesting only because I used a REP block that includes a conditional JMP to break out of the REP, when the current number gets to 1.

    To me, this is interesting only because the code can be smaller and faster :)
    	rep	@.mumble, #0		'repeat the following until it gets to one

	cmp	current, #1	wz	'did it get to one?
  if_E	jmp	#gotToOne          	'okay, display and continue
	drvnot	#scope2
	testb	current, #0	wc	'even or odd
  if_nc	shr	current, #1        	'divide by two if even
  if_c	mov	temp, current      	'multiply by three and add one if odd
  if_c	add	current, temp
  if_c	addx	current, temp
	add	count, #1          	'increment count
	fge	extent, current
.mumble

    That's a clever use of addx! This is even faster, by taking advantage of the fact that 3n+1 is always even: 
    	rep	@.mumble, #0		'repeat the following until it gets to one

	cmp	current, #1	wz	'did it get to one?
  if_E	jmp	#gotToOne          	'okay, display and continue
	drvnot	#scope2
	testb	current, #0	wc	'even or odd
  if_c	mov	temp, current      	'multiply by three and add one if odd
  if_c	add	current, temp
  if_c	addx	current, temp
	addx	count, #1          	'increment count (once if n/2, twice if (3n+1)/2)
	fge	extent, current
	shr	current, #1        	'divide by two (it's always even here; if it was odd, 3n+1 made it even)
.mumble
  • lonesocklonesock Posts: 917
    On the P1 you could test for odd and also see if the value was 1 in a single instruction: 
    shr current, #1 wc,wz,nr
    If C and Z then the value was one, and C is true if it's odd. Is there a 'nr' flag on the P2?

    Jonathan
  • evanhevanh Posts: 16,866
    edited 2019-01-31 00:22
    lonesock wrote: »
    Is there a 'nr' flag on the P2?

    That bit-field was put aside to make room for other features in the instruction set of Prop2. I think one of the biggies was AUGx prefix instructions.
Sign In or Register to comment.