CollatzASM

by Felix Thompson: Y12 Age ~16

Introduction

The Collatz Conjecture is that you can start with any positive integer and end up with 1 by (1) halving each even number in the chain and (2) tripling each odd number then adding 1. (See the program comments). Felix had the good idea of writing in-line assembler code to determine the Collatz chain length of an integer supplied by the user. He also had the ability and perseverance to implement it! The program and the linked Wikipedia page both give the result that the number 27 has a chain length of 111. The program should output the correct chain length as long as no register overflows, and Felix assures us that it will work for all inputs up to 100000.

The Program

program CollatzASM;
{
    Copyright (c) 2012 Felix Thompson

    Licensed under the Apache License, Version 2.0 (the "License"); you may not
    use this file except in compliance with the License, as described at
    http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/
}
{$ASMMODE INTEL}
uses
  SysUtils;
var
  StartInt : Integer;
  Mem1, Mem2, Mem4 : Integer;
  //Mem1 is N
  //Mem2 is for determining if N is odd/even
  //Mem4 is a running total for chain length
begin
  //The following code finds the length of a given number's Collatz chain
  //A Collatz chain is generated by the sequence;
  //          If N is odd    N = (3 * N) + 1
  //          If N is even   N = 1/2 * N
  //This sequence continues until N = 1
  Writeln('Enter an integer to find the length of its Collatz chain.');
  Readln(StartInt);
  asm
    Mov EAX, StartInt
    Mov Mem1, EAX              //Storing the given number into Mem1
   @Start:
    MOV ECX, Mem1
    MOV Mem2, ECX              //Mem2 := Mem1 for determing odd/even
    CMP Mem1, 1                //Checks if N=1
    JE @End
    ADD Mem4, 1                //As N <> 1, there will be another stage of sequence
    AND Mem2, 1                //If the rightmost bit is 1 (odd), Mem2 will become 1 else 0
    CMP Mem2, 1
    JE @Odd                    
    JL @Even                   
   @Odd:
    Mov ECX, Mem1
    ADD ECX, Mem1              //You are sent here if Mem1 (N) is odd-
    ADD ECX, Mem1              //we put Mem1 into ECX, and add Mem1 twice to it-
    ADD ECX, 1                 //tripling it, we then add one and make Mem1 equal this
    MOV Mem1, ECX
    JMP @Start
   @Even:
    SHR  Mem1, 1               //Divide by 2 by shifting one place to the right
    JMP @Start
   @End:
  end;
  writeln(Mem4);               //Finally we output the number of cycles it took for Mem1 = 1
  readln;
end.

Raspberry Pi Version of CollatzASM

program CollatzASM_Pi;
{
    Copyright (c) 2012 Felix Thompson

    Licensed under the Apache License, Version 2.0 (the "License"); you may not
    use this file except in compliance with the License, as described at
    http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/

    Converted for the ARM assembler on the Raspberry Pi by PPS, 2015

}
var
  InputInt, ChainLen: integer;

function ChainLength(StartInt: integer): integer; assembler;
// using r1, r2, r0, r3 for  Mem1, Mem2, Mem4, ECX, respectively

label
  Start, Finish, Even;
asm
  mov r1, StartInt
  mov r0, #0
  Start:
  mov r2, r1  // r2 := r1 for determing odd/even
  cmp r1, #1  // Checks if N = 1
  beq Finish
  add r0, #1  // As N <> 1, there will be another stage of sequence
  and r2, #1  // If the rightmost bit is 1 (odd), r2 will become 1 else 0
  cmp r2, #1
  bne Even    // until is either 1 or 0, if 0 r1 is even, if 1 then r1 is odd
  mov r3, #3  // for multiplication of the odd number
  mul r1, r3  // triple r1
  add r1, #1  // then add one
  b Start
  Even:
  lsr r1, #1  // Divide r1 by 2 by shifting one place to the right
  b Start
  Finish:
end;

begin
  write('Enter an integer to find the length of its Collatz chain: ');
  readln(InputInt);
  ChainLen := ChainLength(InputInt);
  writeln(ChainLen);
  readln;
end.

Programming - a skill for life!

BallTrajectory, BigFibonacci, CollatzASM and MaxCircles by Felix Thompson