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

Groups > comp.arch > #114980

Re: A useless machine

From Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups comp.arch
Subject Re: A useless machine
Date 2026-02-14 21:19 -0800
Organization A noiseless patient Spider
Message-ID <867bseh9c6.fsf@linuxsc.com> (permalink)
References <10mpgtp$32h0n$1@dont-email.me>

Show all headers | View raw

Thomas Koenig <tkoenig@netcologne.de> writes:

> 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?

Amusing.  I predict that ultimately it will be a waste of
effort because the Collatz conjecture is true even though
currently unproven.  Also it seems likely that no mathematical
insights will result from any sort of brute force approach to
disprove it, even if the "brute force" scheme is selective.

If anyone is interested in looking into questions regarding the
Collatz conjecture, I suggest considering a generalization

   f[k](n) = n/2 if n is even, 3n+k if n is odd, for an fixed odd k

Empirically you should quickly find

   There is always a cycle starting at k.  (Duh!)

   There is only one cycle if k is a power of 3.  (This result
   follows from the Collatz conjecture.)

   If k is not a power of 3, there are always at least two cycles,
   and can be more.

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