When working with fixed width registers of finite precision, the choice of underlying base affects the results of arithmetic. As operations are repeated, as in the case of iterated maps, results diverge according to errors dependant on the base.

Introduction

Linear Congruential Generators are iterated maps of the form
x↦ax+cmodm
, with x, a, c, m being machine integers. In our case, we consider maps restricted such that 0 < a and c = 0. We use registers of a finite width and interpret them as unsigned, and thus have for some base
b
,
m
p
b
with
p
being the width of the register. The contents of the register can thus be understood as either a fixed point number in [0, 1) or as an integer. Stephen Wolfram in A New Kind of Science Chapter 4 [1] demonstrates shift maps produce different results when performed in Binary Coded Decimal or binary arithmetic. This paper examines the causes of these differences and the patterns which emerge therein.

Shift Maps

Let us examine the simplest possible form of iterated map, shift maps. For multipliers which have the underlying base as a factor, each digit is shifted one position left, until the system reaches zero for a fixed point. Other multipliers will instead “mine” digits from the residue left behind by multiplication, e.g. for a register of base 10 with width 1,
2100
, but
298
. This “mining” will continuously introduce information beyond the initial condition into the system, causing pseudo-random behaviour.
Out[]=
Here we see the defining characteristics of our exploration: shift maps congruent to the base tend towards zero while others generate pseudo-random triangular patterns. Notice that these are right triangles and that their hypotenuses are slanted in the shift direction, from upper right to lower left.
An integer multiplier gives the simplest pattern of a leftward digit shift. A fractional multiplier gives the same effects but reversed in direction and always terminating at 0. Observe in the first row the now rightward slant of the hypotenuses. Non-integral real multipliers greater than 1 have digit propagation in both directions, resulting in the emergence of scalene triangles in row 2.
Out[]=

Triangular Patterns

In bases with small enough maximum digits that we can make out patterns, there appear black and white triangles at a regular frequency in an ArrayPlot of its evolution over time. To determine the causes of the black and white triangles, let us examine the following example. We select base 2 with a multiplier of 1.5 so that the map
x↦
3
2
x
can be rephrased as
x↦x+x≫1
where “>> n” to indicate a bit shift rightwards by
n
bits. This is done so that the carries can be demonstrated in the classic addition notation.
Out[]=
Take the white triangle at lines 8 to 13. We see steady ingress from the left as the 1.5 multiplier shifts components down and right. Ingress from the right is less common and occurs as carries push leftwards. Observe at row 7 the black white checker-boarding. The 1.5 multiplier adds the row shifted right by one digit, this creates a row of pure black cells, and a chain of carries clears the next row. Below we decompose the map to addition as previously described, which allows us to visualize the chain of carries which produces the white row.
Out[]=
Black triangles occur when there is no feed from the right to trigger the carries. Instead, the black block forms and dissolves slowly since the preceding rows provide enough digits that carries “skip” across instead of causing a domino effect.
Observe also the black triangle from lines 5 to 7. Starting from line 4, there is the checker-boarding which preceded the white triangle, but we observe that there is no carry to trigger the domino reaction we saw before. Instead, once the black section is established, the carries “skip” over a solid base to the left, slowly eroding the triangle from both directions as no carry feeds in from the right and carries escaped to the left.
Out[]=
Observe that the grey rows preceding triangles in base 3 are of the same type as the checkerboards in base 2. In both cases the row before the triangle serves to setup the following row in a volatile state which is either triggered or left to diffuse.
Out[]=
This ability to analyze local behaviour to find triangles does not scale up well to larger multipliers (
a≫b
). The large multiplier reduces locality and means that the rows of the triangle are hard-pressed in staying together. Triangles are also rarer in bases with larger maximum digits, but are better distributed.
Out[]=

Locality & Divergence

Divergence from Finite Precision

Evolve the first five powers of two with the same initial condition and approximately the same precision:
When the systems compose evenly so that the precisions are multiples of each other, they reproduce the same results. When the rounding brings it to the nearest integer, the slight change in precision disrupts the system. Thus, one cannot always reproduce the same result at the same precision with a theoretically base compatible base.

Value Propagation

Evolve from two starting conditions mutated by a bit flip then sum, even values indicate agreement, odd values, disagreement:

Further Work

Orbits & Transitions

We may observe the state transition graph from our nested maps by examining representative graphs of limited precision. Since the number of states grows exponentially as the register widens, we must look at very reduced precisions. Each starting position follows a path until it reaches a stable orbit. These paths grow longer as the representative capacity of the register increases.

Logistics Map

Unconstrained Parameters

Negative multipliers produce striped patterns:

Prefix Randomness

We display the randomness of the prefix as both a ratio of zeroes to ones, and as a walk where zero is treated as -1.
Observe below the ArrayPlot of the first 100 steps with the leading digit in red, and a ListLinePlot of the walk with zero as a decrement for the first 1000 steps.

Implementation

Concluding Remarks

The triangular patterns are the simple result of the choice of multiplier and their patterns can be described as such. As we would expect, the pseudo-random patterns create sequences with a domino effect that clears a broad column. This column is then filled according to the direction of value propagation. That the triangles occurred from the pseudo-randomness and not a defect therein surprised me since I had expected some greater order to them.

Acknowledgments

This project was made possible solely through the aid of Willem Nielsen and his knowledge of the Wolfram Language. Additionally, Stephen Wolfram was essential in introducing me to this topic. This report would not exist without their aid.

References

1
.
Wolfram (2002), A New Kind of Science. Wolfram Media. https://www.wolframscience.com/nks.
2
.
Knuth (1997), The Art of Computer Programming. Addison-Wesley Publishing Company.

Cite This Notebook

Investigating Register Base Effects on Iterated Map Behaviour​
by Lorenzo Ravaglia​
Wolfram Community, STAFF PICKS, July 9, 2025
​https://community.wolfram.com/groups/-/m/t/3496270