# Fortran bit intrinsics for fast Collatz sequence computation

**URL:** <https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237>\
**Category:** Uncategorized\
**Created:** [February 20, 2025, 6:08pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237 "2025-02-20T18:08:42Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![mecej4](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/mecej4/32/855_2.png) [@mecej4](https://fortran-lang.discourse.group/u/mecej4)\
**Post date:** [February 20, 2025, 6:08pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237/1 "2025-02-20T18:08:42Z")

</div>

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

```auto
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.

```auto
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

```

---

<div class="post-metadata">

**Author:** ![mecej4](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/mecej4/32/855_2.png) [@mecej4](https://fortran-lang.discourse.group/u/mecej4)\
**Post date:** [February 20, 2025, 6:16pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237/2 "2025-02-20T18:16:51Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mecej4](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/mecej4/32/855_2.png) [@mecej4](https://fortran-lang.discourse.group/u/mecej4)\
**Post date:** [February 22, 2025, 3:16pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237/3 "2025-02-22T15:16:55Z")

</div>

```auto
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:

```if
   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](https://fortran-lang.discourse.group/uploads/short-url/q4hczyZyGSgbXXbTn5A8yaORONe.f90) (940 Bytes)

---

<div class="post-metadata">

**Author:** ![ivanpribec](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/ivanpribec/32/3290_2.png) [@ivanpribec](https://fortran-lang.discourse.group/u/ivanpribec)\
**Post date:** [February 24, 2025, 10:02pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237/4 "2025-02-24T22:02:46Z")

</div>

[This paper](https://www.scitepress.org/Papers/2021/105571/105571.pdf) (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](https://gist.github.com/ivan-pi/6097d71bb1512b967008c0362f6f40cc) (assumes MacOS) at some point (without the Collatz conjecture part).

---

<div class="post-metadata">

**Author:** ![mecej4](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/mecej4/32/855_2.png) [@mecej4](https://fortran-lang.discourse.group/u/mecej4)\
**Post date:** [March 7, 2025, 4:27pm UTC](https://fortran-lang.discourse.group/t/fortran-bit-intrinsics-for-fast-collatz-sequence-computation/9237/5 "2025-03-07T16:27:16Z")

</div>

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)

```auto
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
```