Re: A useless machine

From	Michael S <already5chosen@yahoo.com>
Newsgroups	comp.arch
Subject	Re: A useless machine
Date	2026-02-15 18:33 +0200
Organization	A noiseless patient Spider
Message-ID	<20260215183335.0000649e@yahoo.com> (permalink)
References	<10mpgtp$32h0n$1@dont-email.me> <10ms1rm$3s9f4$1@dont-email.me> <20260215153526.00005240@yahoo.com>

Show all headers | View raw

On Sun, 15 Feb 2026 15:35:26 +0200
Michael S <already5chosen@yahoo.com> wrote:

> On Sun, 15 Feb 2026 03:58:28 -0500
> Robert Finch <robfi680@gmail.com> wrote:
> 
> > On 2026-02-14 4:57 a.m., Thomas Koenig wrote:  
> > > Some people are throwing large amounts of computing power at
> > > trying to disprove the Collatz conjecture.  Graphics cards have
> > > sped this up enormously.
> > > 
> > > (A reminder, if any is needed:  From a starting number n, the
> > > transformation, recursively applied,
> > > 
> > > 
> > >     f(n) = 3*n+1, if n is odd; =n/2 if n is even.
> > > 
> > > is conjectured to always reach 1 for any positive integer 1).
> > > 
> > > All the work is done on general-purpose hardware, which has many
> > > capabilities that are not needed, and consume area and power that
> > > special-purpose hardware would not need.  Also, the hardware
> > > is limited to 64-bit integers, and the range of tested numbers
> > > is now up to 2^71, so
> > > 
> > > What could specialized hardware look like?
> > > 
> > > The central part could be a unit which is handed a block of
> > > numbers to check, for example a range of 2^32 numbers.  The
> > > current records for number of iterations and maximum number
> > > reached would also be stored in that unit.
> > > 
> > > In that unit, the calculaiton would be performed by a combination
> > > of adder and shifter.  The input would always be odd (so the last
> > > bit could be dropped), and it would calculate (3*n+1)>>ctz(3*n+1).
> > > 
> > > The adder would compute (3*n+1)/2, and would be specialzed 128-bit
> > > adder.  Why specialized?  The logic is far less complex than a
> > > general-purpose adder.  For example, a two-bit adder has the
> > > formula
> > > 
> > > y1 = (!a1&a0) | (!c_in&a1&!a0);
> > > y0 = (c_in&!a1&!a0) | (!c_in&a1&!a0) | (a1&a0);
> > > 
> > > and its propagate and generate bits are
> > > 
> > > p = (a1);
> > > g = (a1&a0);
> > > 
> > > The maximum number of trailing zeros after the (3*n+1)/2 step is
> > > three and can be determined cheaply from bits <3:1> of the input,
> > > so the input to the shifter (two levels only) can be provided
> > > in parallel.  The machine would be designed that adding and
> > > shifting can be done in a single cycle.
> > > 
> > > The number of iterations would be tracked; if larger than a
> > > prevous record, the calculation would terminate with a
> > > corresponding signal to the outside world.
> > > 
> > > Also, each cycle, the result from the previous round would be
> > > compared against the input value.  If it is lower, the next number
> > > would be chosen.  Finally, the number reached would be checked
> > > against the previous, pre-set maximum, with would also signal to
> > > the outside world.
> > > 
> > > Which numbers to chose?  It is well known that only certain
> > > numbers with remainders modulo 2^n are interesting.  The number
> > > can be seen on OEIS A076227.  For example, modulo 2^10, only 64
> > > numbers are "interesting", or 6.25% (but only eight bits would
> > > be needed to store them because the last two are always one).
> > > Modulo 2^16 would be 734 numbers, or 3.22%, so this would cut the
> > > amount of numbers to be checked by half.  One would use a small
> > > ROM, I presume. The number of bits would be a tradeoff between
> > > area and amount of compuation. My current guess would be that
> > > 2^10 could be a sweet spot.  One third of the numbers would
> > > further be excluded by checking for divisiblity by three.
> > > 
> > > The problem is embarassingly parallel.  One could chose a size so
> > > each parcel is calculated in a few seconds or even minutes. to
> > > avoid having to avoid a large amount of communication with the
> > > outside.
> > > 
> > > Because all units would be working all the time, and if one has
> > > a smaller unit one could simply build more of them, I suspect that
> > > power would be the main limiting factor.  An adder design that
> > > might not be very fast, but uses lower power, low voltage and low
> > > frequency would be beneficial.
> > > 
> > > Comments?
> > >     
> > I wonder how difficult it would be to implement a parallel tester in
> > an FPGA. It looks simple enough and there are hundreds of DSP
> > blocks available to use. Could test in blocks of hundreds of
> > numbers at a time. Running at 100 MHz * 200 tests at a time = how
> > long to get to 2^71?
> >   
> 
> I am not totally sure what exactly you are asking, but if you are
> asking about how much time it takes at that rate to do 2**71
> iterations then the answer is ~3743 years.
> But you probably already figured it out yourself.
> 
> Of course, brute force demonstration of correction of conjecture for
> all numbers in range 1 to 2**71 will take more steps than 2**71. And
> it is unknown how much more.
> 

"Unknown" is a correct theoretically answer, but I can provide a very
educated guess that on average it would take ~500 steps and the worst
case would not exceed 2000 steps.
So, bad news are that overall it will take more than a million years on
your machine. And good news are that it'll take less than 2 million
years.

Thread

A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-14 09:57 +0000
  Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 18:48 +0000
    Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-14 20:18 +0100
      Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 21:22 +0000
        Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-14 13:30 -0800
        Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 12:50 +0100
          Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 13:48 -0600
            Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-21 21:40 +0100
              Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 15:17 -0600
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 04:50 -0600
              Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:01 -0700
            Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 14:43 +0100
              Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 12:38 -0600
                Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:51 +0100
                Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-26 01:27 +0000
                Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-26 09:21 +0100
                Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:11 -0700
      Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:58 +0100
      Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 12:27 -0600
        Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 15:14 +0100
      Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-22 11:41 -0500
        Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:53 +0100
          Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-23 10:52 -0500
  Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-14 21:19 -0800
  Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 03:58 -0500
    Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 13:14 +0100
      Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 15:46 +0000
      Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 10:56 -0500
        Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-15 19:16 +0000
          Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:40 +0100
            Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-26 19:31 +0000
        Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-18 18:22 +0200
          Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-18 22:56 -0500
            Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 12:10 +0200
              Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-21 01:56 -0500
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 19:23 +0200
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 20:36 +0200
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 10:46 +0200
                Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-22 12:45 +0100
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 16:35 +0200
                Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:12 -0500
                Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:47 -0500
                Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-21 15:39 -0500
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 03:16 +0200
                Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-22 14:48 -0500
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 23:25 +0200
            Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-19 11:51 +0100
              Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 23:12 +0200
                Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-20 15:11 +0100
            Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-19 15:27 -0500
              Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-20 11:41 +0200
              Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 18:41 -0600
                Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-23 11:10 +0000
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-23 17:24 -0600
                Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 06:44 +0000
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 01:38 -0600
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 03:16 -0600
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 04:52 -0600
                Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 11:16 +0000
                Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 13:19 -0600
                Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:14 -0700
          Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-20 08:01 +0000
    Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 15:35 +0200
      Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 18:33 +0200
        Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:19 +0000
          Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:31 +0200
            Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 15:41 +0200
              Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 18:17 +0200
    Re: A useless machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-02-15 22:41 +0000
  Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:52 +0100
    Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 16:45 +0000
      Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 18:01 +0100
        Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:42 +0000
          Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:59 +0100
            Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 21:53 -0500
              Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:40 +0200
                Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 20:34 +0200
              Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-16 16:08 +0100
  Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-16 07:50 -0800
    Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 18:31 +0200
    Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-18 21:56 +0100

csiph-web