Collatz: Uses conditional JMP within REP block

tomcrawford

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.

TonyB_

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 

Electrodude

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 

lonesock

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

evanh

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.