Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #114987

Re: A useless machine

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

Show all headers | View raw

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.

> I wonder if the calculation can be broken down further. Numbers are
> all just defined by rules. I wonder if some calculus may apply. Limit
> of function approaches one for a finite number of steps. There may be
> a whole range of algorithms, is there one for the number two? Then
> the number three?
> 
> Occasionally I have made useless machinery. Great puzzle work. Made
> the game of life in hardware.
>

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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