This project explores low level parameterized base N computing models through simulation and visualization, revealing patterns and providing insight for converging number sequences like 3n+1 (Collatz Conjecture). A flexible computing model and base N number system were designed, allowing for full parameterization and easy base conversion. Programming the computer involved a custom CPU instruction set and an assembler, built to convert assembly code into base N machine code. During experimentation and testing, programs were randomly created in multiple bases, revealing converging number sequences specific to each base. These programs were then run along with the 3n+1 sequence, where the CPU states were monitored and recorded during each cycle to create a multiway graph and animated graphics. The ultimately aims to demonstrates a flexible framework for base N computing and a base N physically implementable number system, including the potential insights it can reveal for convergent sequences and the Collatz conjecture.

Introduction

In the realm of digital computation, computers have become inseparable from the base 2 binary system, with 1s and 0s being an incredibly efficient and reliable way to represent numbers and preform operations on electric circuits. Yet in the world of numbers, practically any base can be used to represent them, which prompts the interesting question: What if we go beyond the standard binary system and explore base N computation? This research dives into this theoretical space by establishing a base N number system and a base N computer model, then explores some of the interesting aspects and visualizations of base N computation, including using it to generate base N number sequences.

How does a computer work?

At a fundamental level, computers operate by simply reading very basic instructions from memory such as moving, storing, or adding numbers. With a proper set of these basic instructions, practically any computation can be done.

Parts of a Computer

◼
  • Memory: A large array of indexed values, allowing reading and writing.
    • ◼
  • CPU: Performs a series of instructions from memory.
    • ◼
  • Registers: Small temporary storage locations inside the CPU for data, instructions, and addresses.
    • ◼
  • Program Counter: A register which stores the memory address for the next CPU instruction.
    • ◼
  • Instruction Register: A register which stores the current instruction.
    • ◼
  • Flag Register: A special type of register which stores CPU flags. Flags can include negative number, zero, less than, or others, which tell the processor about the result of a computation and allow for control flow.
    • ◼
  • ALU: Arithmetic and Logic Unit which performs all the arithmetic and logic operations for the computer, often outputting and taking values to and from registers.
    • ◼
  • Control Unit: The “conductor” of the CPU. It decodes and interprets an instruction then sends all the necessary signals to get the other CPU components to carry out the instruction.
    • ◼
  • Accumulator: While often part of the ALU and not always prevalent in CPU designs, the accumulator is a type of register used in very simple single data register designs, which stores the last output from the ALU for further processing or as a temporary storage location

    • Instruction Cycle

    1
    .
    Instruction Fetch: CPU retrieves the next instruction from memory at the address stored in the program counter. The instruction is loaded into the instruction register and the program counter is incremented to point to the next instruction in memory.
    2
    .
    Instruction Decode: The control unit decodes the instruction now stored in the instruction register. Decoding involves breaking down the instruction into it’s parts to determine the desired operation and whatever parameters passed in with the operation.
    3
    .
    Execution: The control unit sends signals to relevant parts of the CPU to execute the instruction. This can include arithmetic operations, logic operations, memory operations, data movement, etc.

    Base N number system

    A number's base b refers to the number of unique digits in range [0,b-1] used to represent the number. For example in base 10, digits can be from 0-9, and in binary or base 2, digits can be 0-1. Having a base N number system starts with defining a variable for the base and the number of digits that numbers have (defining this necessary from a physical computer implementation standpoint).
    Define variables
    In[]:=
    base=2;​​numberSize=16;

    Base N Number Data Type

    Because of the restriction for digits to be in range [0,b-1], defining a digit data type that restricts number values within that range will be helpful. The digits will only represent singular base N digits in the number system.
    Constructor, helper and visualization functions for the digit data-type
    In[]:=
    newDigit[x_Integer]:=digit[x]/;0<=x<base;​​newDigit[x_Integer]:=Throw["Digits must be in range [0,9]"]​​​​digitValue[digit[x_]]:=x;​​digitVisualize[n_digit]:=GrayLevel[digitValue[n]/(base)]
    In[]:=
    Row[{digitVisualize[newDigit[0]],digitVisualize[newDigit[base-1]]}]
    Out[]=
    A base N number can then be defined as a list of digits. In order to support negative numbers, I will use the number's base N compliment, meaning that a negative number n is represented by base^size + n, size being the size of the number in digits. This is similar to the IEEE standard for integers and allows for standardized arithmetic algorithms that have built in support for negative and positive numbers without needing if statements.
    Recursive helper function for converting a number into base N
    In[]:=
    newDigitNumRecursion[n_Integer] /; n < base := {n}​​newDigitNumRecursion[n_Integer] := Append[newDigitNumRecursion[Quotient[n, base]], Mod[n, base]]
    Constructor definition for the digitNum data-type
    In[]:=
    newDigitNum[n_Integer,size_Integer]:=Throw["size is too small to create a digit num with the specified integer"]/;Abs[n]>Floor[base/2]*Power[base,size-1]​​newDigitNum[n_Integer,size_Integer]:=digitNum@@Table[newDigit[0],size]/;n==0​​newDigitNum[n_Integer,size_Integer]:=digitNum@@digit/@PadLeft[newDigitNumRecursion[n],size]/;n>0​​newDigitNum[n_Integer,size_Integer]:=digitNum@@digit/@PadLeft[newDigitNumRecursion[base^size+n],size]/;n<0

    Utilities

    Some digitNum utilities can be helpful for the number system such as converting them into standard lists of Integers, a MatchQ method called digitNumQ, and a copy method.
    Define matching function, list conversion, and copy functions.
    In[]:=
    digitNumQ[num_digitNum]:=MatchQ[num, digitNum[___digit]]​​digitNumToList[dn_digitNum]:=digitValue/@List@@dn​​digitNumCopy[from_digitNum,to_digitNum]:=Throw["Destination digit num cannot be smaller than the digit num you are copying"]/;Length[from]>Length[to]​​digitNumCopy[from_digitNum,to_digitNum]:=PadLeft[from,Length[to],newDigit[Floor[digitValue[from[[1]]]/base*2]*(base-1)]]

    Integer Conversion

    Converting from base N back to a base 10 wolfram language integer involves iterating through each digit from right to left and multiplying it by the base raised to the power of the digit's index. Negative values are accounted for by looking at the first digit and checking if it's larger or equal to base/2, if so, the number must be negative and the negative complement is computed.
    Integer conversion method
    In[]:=
    digitNumToInteger[dn_digitNum]:=Fold[(#1*base + #2) &, 0, digitNumToList[dn]]-Floor[digitValue[dn[[1]]]/base*2]*(base^Length[dn])

    Integer Arithmetic

    Rather than converting base N numbers to integers and preforming arithmetic using built in functions, in order to make the simulation more accurate to something that could be implemented in real life, I used carrying. Additionally, due to the way negative numbers are represented, the basic carrying based addition, subtraction, and multiplication algorithms account for sign changes and everything properly without the need for hard coded if statements. Lastly, rather than having a divide function, I opted for the shift function which shifts the given digitNum by n digits left or right, effectively multiplying or dividing by the base.
    Arithmetic function definitions including addition, subtraction, incrementing, digit shifting, and multiplication
    In[]:=
    digitNumAdd[a_digitNum,b_digitNum]:=Module[{carry=0,maxLength=Max[Length[a],Length[b]]},​​digitNum@@(digit/@Reverse[MapThread[Module[{n},n=Mod[#1+#2+carry,base];carry=Floor[(#1+#2+carry)/base];n]&,{Reverse[PadLeft[digitNumToList[a],maxLength,Floor[digitValue[a[[1]]]/base*2]*(base-1)]],Reverse[PadLeft[digitNumToList[b],maxLength,Floor[digitValue[b[[1]]]/base*2]*(base-1)]]}]])]​​​​digitNumSub[a_digitNum,b_digitNum]:=Module[{carry=0,maxLength=Max[Length[a],Length[b]]},​​digitNum@@(digit/@Reverse[MapThread[Module[{n},n=Mod[#1-#2-carry,base];carry=If[#1-#2-carry<0,1,0];n]&,{Reverse[PadLeft[digitNumToList[a],maxLength,Floor[digitValue[a[[1]]]/base*2]*(base-1)]],Reverse[PadLeft[digitNumToList[b],maxLength,Floor[digitValue[b[[1]]]/base*2]*(base-1)]]}]])]​​​​digitNumIncrement[a_digitNum]:=Module[{carry=0},​​digitNum@@(digit/@Reverse[MapThread[Module[{n},n=Mod[#1+#2+carry,base];carry=Floor[(#1+#2+carry)/base];n]&,{Reverse[digitNumToList[a]],PadRight[{1},Length[a]]}]])]​​​​digitNumShift[a_digitNum,digits_Integer]:=If[digits>0,PadRight[Drop[a,digits],Length[a],newDigit[0]],PadLeft[Drop[a,digits],Length[a],newDigit[0]]]​​​​digitNumMultDigit[a_digitNum,m_digit]:=Module[{carry=0},​​digitNum@@(digit/@Reverse[Map[Module[{n},n=Mod[#*digitValue[m]+carry,base];carry=Floor[(#*digitValue[m]+carry)/base];n]&,Reverse[digitNumToList[a]]]])]​​digitNumMult[a_digitNum,b_digitNum]:=Module[{sum=newDigitNum[0,Max[Length[a],Length[b]]]},Fold[digitNumAdd,sum,List@@MapIndexed[digitNumShift[digitNumMultDigit[a,#],#2[[1]]-1]&,Reverse[b]]]]
    Verifying the equation 123-32=91 using the digitNum datatypes
    In[]:=
    digitNumToInteger[digitNumAdd[newDigitNum[123,10],newDigitNum[-32,9]]]
    Out[]=
    91

    Boolean Arithmetic

    Because of the non binary nature of the base N number system, it's a little bit difficult to define booleans and boolean functions. However, I came up with a relatively effective method which works with base N numbers and supports boolean functions. If true is represented by any positive integer and false is represented by zero, OR can simply be represented using the addition function and AND can be represented using the multiplication function.
    Function for interpreting a digitNum as a boolean
    In[]:=
    digitNumToBoolean[dn_digitNum]:=!And@@(#===digit[0]&/@dn)
    Grid for a boolean arithmetic table
    In[]:=
    Grid[Join[{{"a","b","a&b","a|b"}},{digitNumToBoolean[#[[1]]],digitNumToBoolean[#[[2]]],digitNumToBoolean[digitNumMult[#[[1]],#[[2]]]],digitNumToBoolean[digitNumAdd[#[[1]],#[[2]]]]}&/@Tuples[{newDigitNum[base-1,5],newDigitNum[0,5]},2]],Frame->All]
    Out[]=
    a
    b
    a&b
    a|b
    True
    True
    True
    True
    True
    False
    False
    True
    False
    True
    False
    True
    False
    False
    False
    False

    Visualization

    Tiling the visualizations from individual digits from before, a number can be visualized, as well as a list of numbers.
    Visualization functions for the digitNum data-type
    In[]:=
    digitNumVisualize[dn_digitNum]:=Image[List/@List@@digitVisualize/@dn,ImageSize->Medium]​​digitNumListVisualize[digitNumList_List]:=Image[(List@@digitVisualize/@#&)/@digitNumList,ImageSize->Medium]
    Each row of pixels is a base N number.

    Computer Design

    When designing a basic CPU, I had the choice of either going for a register based design, which can provide more efficiency for less operations for added complexity, or an accumulator based design, which is much simpler and easier to implement. I ultimately settled on an accumulator based design because the efficiency gain from having a multiple register design isn't worth the extra complexity for my purposes.

    Instruction Set

    The first step to designing a base N CPU is to define the instruction set that you want the CPU to be able to support. More instructions can be added later but it's important to start with enough where you can essentially create any program. I eventually settled on a reduced instruction set computer (RISC) design as it would provide the most simplicity in implementation and is sufficient for this project. [1]
    Instruction set list definition
    Each instruction in the instruction set will take one argument. For most of the instructions, the argument is a memory address. The following is descriptions for each instruction
    LOAD X: Loads the value from the accumulator into memory address X
    MOV X: sets the value of the accumulator to X
    STORE X: stores the value at memory address X into the accumulator
    ADD/SUB X: Adds or subtracts the value at memory address X to or from the accumulator and stores the result into the accumulator
    MULT X: Multiplies the value in the accumulator by the value at address X and stores the result into the accumulator
    SHFT X: Shifts the value in accumulator by the number of places specified by the value at memory address X and stores it into the accumulator
    JUMP X: Sets the program counter to memory address X so it will be executed on the next instruction cycle
    HALT X: Stops instruction cycle, X can be any number
    NOOP X: Performs no operation, X can be any number
    JZ X: Jumps to memory address X if the zero flag is set
    JNZ X: Jumps to memory address X if the zero flag isn't set
    JN X: Jumps to the memory address X if the negative flag is set
    PRNT X: Prints the value at memory address X

    Programming with Base N Assembly

    The instruction set used isn't set in stone and may be subject to change. However with the current RISC design, writing programs often requires some clever techniques and basic understand of the CPU architecture. However, it's quite easy to pick up due to the limited instruction set and basic accumulator based CPU architecture. Some sample programs are below

    3 n + 1 sample program

    The 3n+1 hailstone problem, also known as the Collatz conjecture, is an interesting sequence created starting from any positive integer, halving the number if it's even, or multiplying it by 3 and adding 1 if it's odd, until the sequence eventually reaches 1. This program written in base N assembly generates the hailstone sequence from a specific starting value, utilizing base 2 digit shifting in place for division.
    Hailstone program string definition

    Flags

    CPU flags, or condition flags, are stored in a register, where digits represent true or false and hold specific information about the results of a computation, such as whether a calculation resulted in zero or a negative number. I wanted to have support for greater than/less than operations, as well as equal operations, which could be supported by having a negative and zero flag. Additionally, when the cpu reads the halt instruction it needs to be able to carry that information on to the next clock cycle to that it can stop.
    Flags list definition

    Assembler

    In order for the CPU to interpret the instructions, they can't stay as text, and must first be converted into base N machine code because the CPU components can only recognize base N digits. The process of converting the text instructions, assembly code, into machine readable code, assembling, and is performed by an assembler. Instructions can be converted into base N digitNums by simply numbering each instruction and replacing them with their digitNum equivalent. This was relatively simple to code considering the use of a RISC, however more complex assembly languages often require very complex assemblers.
    assembler function definition

    Computer Architecture

    The key to making a usable and intuitive base N computer was having it be parameterized, flexible and work with any base N number system. This was achieved with a newComputer function, which generates a base N computer, automatically computing the required registers sizes to support the desired amount of RAM, the given instruction set, and the base. The CPU's instruction set, it's flags, and the assembled machine are passed in, along with the number of ram addresses it's able to support.
    computerState constructor function.
    Create a new computer
    With a custom computerState data-type that stores all the computer's data, a visualization method can be made that simply takes in the computerState expression.
    Computer state visualization function definition
    The current computer visualization is configured in the following order:
    {Memory block, instruction register, program counter, flags, accumulator}
    Visualizing the current computer
    The mess of pixels around the top of the memory block is the program loaded into memory.

    Computer States

    In order to visualize the progression of the computer, it's helpful to define a way to represent a computer state in a simple way. This was achieved by vectorizing the base N computer into a single list of integer values, containing all the CPU register data as well as memory. However, not all parts of the program have to be included in the vectorization and excluding specific elements can have a significant effect on the visualized product, allowing one to focus on certain aspects of the computation.
    Function for vectorizing the computer state with the given elements excluded
    Get the computer state of the defined computer

    Instruction Cycle Implementation

    The CPU instruction cycle can be thought of as a function that simply computes the next computer state. The function goes through all stages of the fetch-decode-execute cycle in base N.
    Function for recursively computing the next computer state, returning the list of states that the computer goes through.

    Running the Computer

    With everything built, the computer can finally be run on the hailstone problem. My first demonstration will be a 16 bit base 2 computer, as a type of control.
    Set the base, number size, and running the computer
    Looking at the CPU state animation of the 3n+1 Collatz Conjecture sequence, specifically the memory block on the left, the moving line of digits is the current number in the sequence. They appear to be moving to the right, pushed left, then continue moving to the right. This is because division by 2 in a base 2 system is the same as a rightward shifting operation, and when the number cannot be shifted more, the rules behind the Collatz Conjecture say to multiply the number by 3 and increment it by 1. This shifts the value toward the left where the process is allowed to continue until there is only one bit left.
    Animate the computer state visualizations

    Graphing Computer States

    With the computer state functions defined earlier, graphing and visualizing the computer as it progresses through a program should be simple. For these demonstrations, the red edges are the ones closer to the beginning of the program and the blue edges are closer to the end of the program.
    Function for creating a 3d graph of computer states
    Graphing the computer states excluding memory from vectorization results in an interesting graph. However due to the inclusion of the program counter in the computer states, the graph mainly just highlights the program structure rather than the program's outputs or intermediate calculations. The converging points show different parts of the control flow, splits being where the program either jumps to the even or odd case, and the small dense blue lines being where the program loops back to the next iteration.
    Graph the computer for the 3n+1 program excluding memory differences
    Another version however, excluding the program counter from the computer state vectorization shows some more interesting results. The octopus like graph has two main converging parts, being the two cases, an odd or even number. The converging point with the "tentacles" represents the even case, as dividing an even number often results in another even number, and therefor edges loop back to their original position in the graph. On the other hand, for the odd case, because multiplying by an odd number by 3 and adding 1 always results in an even number, edges at the octopus's head always return to the tentacles, resulting in the round head shape.
    Graph the computer for the 3n+1 program excluding memory and program counter differences

    Base 4 demonstration

    Now creating the base 4 computer for the program and running it.
    Set the base, number size, and running the base 4 computer
    The computer visualization now has more shades of gray, as digits are able to hold 4 different values. Additionally, looking at the moving value in the memory block, which again stores the current number in the sequence, it is seen to follow a similar pattern as the 3n+1 sequence. It’s shifted right as much as possible, pushed left, then continues right until there’s only one digit left.
    Animate the computer state visualizations
    Graph the base 4 computer for the 4n+4 program excluding memory differences
    In the base 4 system, you see four converging points, each one representing n%base. The center converging point is when n%base = 0. Despite the 4n+4 rule being much simpler and more intuitive than the 3n+1 rule, it shows similar patterns as the binary 3n+1 Collatz Conjecture graph.
    Graph the base 4 computer for the 4n+4 program excluding memory and program counter differences

    Base 10 demonstration

    I’ll use the same type of sequence as the base 4 demonstration but switching to base 10. This time the sequence is 10n-10 for non 10 divisible numbers.
    Now creating the base 10 computer for the program and running it.
    Set the base, number size, and running the base 4 computer
    Animate the computer state visualizations
    Graph the base 10 computer for the 10n-10 program excluding memory differences
    In the base 10 system, you see ten converging points, again representing each modulus of 10. The center converging point is when n%base = 0.
    Graph the base 10 computer for the 10n-10 program excluding memory and program counter differences

    Conclusion and Future Work

    The exploration of base N computing models and simulations has yielded fascinating insights into the behavior of number sequences such as the Collatz Conjecture in different number bases. The custom-designed and flexible computing framework has demonstrated working examples of base N computing, but it also shows its potential for uncovering patterns and relationships in numerical sequences and computation. The visualizations and graphs, created from recording CPU states, create an insightful representation of the execution of programs in a base N computer. This helps in understanding the underlying behaviors and patterns specific to each base, and ultimately provides interesting insights into these number sequences. The base 4 and base 10 results, in particular, had close connections and the similar patterns with the binary 3n+1 Collatz Conjecture visualizations, suggesting that the principal behind the Collatz Conjecture may apply across different number bases.

    Future Work

    This project has opened up multiple avenues for future exploration. The first is a deeper examination of the results obtained for other bases and the generalizations that can be derived. Hopefully we can help reveal any universal properties or structures common to all bases in the context of computation as well as features specific to certain bases.
    ​
    Secondly, the use of random program generation in this project was limited to random number generation with a fixed program format, which helped in the discovery of the other converging sequences but could still be extended to a wider exploration of computational irreducibility and sequences like 3n+1.
    ​
    Finally, the development of my base N computing framework allows for other base N computational projects and visualizations, though it can still use some work. Adding more complex instructions or functionality, exploring memory management techniques, or a compiler for the base N assembly could yield even more depth and utility to the base N computation model.

    Acknowledgements

    I would like to thank Stephen Wolfram and the WSRP staff for the opportunity to work on this project. I would also like to thank my mentor Eric Rimbey for his continual support throughout my work.

    References

    1
    .
    Shaout, Adnan & Eldos, Taisir . (2003). On the Classification of Computer Architecture .

    CITE THIS NOTEBOOK

    Base N computer simulation: visual analysis and Collatz conjecture​
    by Tyler Rose​
    Wolfram Community, STAFF PICKS, July 13, 2023
    ​https://community.wolfram.com/groups/-/m/t/2964817