Fortran bit intrinsics for fast Collatz sequence computation

1

The intrinsic functions shiftr and trailz can be very helpful in the computation of Collatz sequences. Given a current value x, an odd number, we can compute the next value, y, using

if (btest(x,0)) then
   v=3*x+1
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz); x =y

An advantage of this code is that the result, y, is also odd, which facilitates continuation of the calculation of the sequence. These lines can be placed in a DO loop to calculate an entire sequence with a specified initial value.

x=27
do i=1,41 ! 41 iterations are known to take us to 1
if (btest(x,0)) then
   v=3*x+1
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz)
print *, i,x,v,y; x =y
if(x.eq.1)exit !assumes truth of Collatz conjecture
end do
1 Like
2

If, instead of starting with 27, we start with 49, we obtain a startling result: After just two 3x+1 steps and the appropriate number of halvings, we obtain 7, which is the square root of 49! Similarly, starting with 1331, after 12 iterations we obtain its cube root, 11; starting with 169, we obtain 13, its square root, after 14 iterations. Starting with INT(10^5 \pi) = 314159, we reach 1 after 64 iterations. The starting values 3^3=27 and 10^3=1000 generate the same sequence of odd numbers, terminating in 1.

3 
x=27
do i=1,41 ! 41 iterations are known to take us to 1
if (btest(x,0)) then
   v=3*x+1
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz)
print *, i,x,v,y; x =y
if(x.eq.1)exit !assumes truth of Collatz conjecture
end do

Yet another speed up depends on avoiding the multiplication by 3:

   v=shiftl(x,2)-(ibclr(x,0)) !v=4*x-(x-1)
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz)

The attached source file contains these improvements. It reads a starting value and outputs the Collatz sequence that starts with that value.
nextcoll.f90 (940 Bytes)

2 Likes
4

This paper (PDF, 361 kB) uses the Collatz conjecture to demonstrate some advantages offered by the virtual memory and CPU memory management unit (MMU) for multi-threaded append operations. I prepared a Fortran MWE (assumes MacOS) at some point (without the Collatz conjecture part).

2 Likes
5

A further improvement may be made by noting that (3x+1)/2 may be computed as x+shiftr(x,1)+1 when x is odd, since 3x+1 = 2x+(x+1)

program scoll
    implicit none
    integer :: i,x,xn,y,v,x0,lx,nz,ITRLIM=50
    read *,x0; x=x0
    if(mod(x0,2).ne.1)stop 'x0 must be odd'
    print *,'Iter       x    xn '
    do i=1,ITRLIM
       !lx=shiftr(x,1)
       y=x+shiftr(x,1)+1 !(3x+1)/2=(2x+x+1)/2 = x+lx+1
       
       nz=trailZ(y); xn=shiftr(y,nz)
       print '(i3,4x,2i6,4x,i3)',i,x,xn
       x=xn
       if(x.eq.1)exit
     end do
     if(x.eq.1)then
        print *,'1 reached after ',i,' iterations'
     else
        print *,'1 not reached in ',i,' iterations'
     endif
end program scoll