From: tkoenig@netcologne.de   
      
   David Brown  schrieb:   
   > On 15/02/2026 09:58, Robert Finch wrote:   
   >   
   >> 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?   
   >>   
   >   
   > One of the nice things about this is that you don't need DSP blocks - it   
   > all works well with very simple operations well-suited to an FPGA.  Your   
   > calculation blocks would hold an n-bit number (wider than the number you   
   > are testing for, since rounds of the Collatz function can grow a lot)   
   > and a counter.  Initialise the block to the number you want to test.   
   > For each round, check the LSB.  If it is 0, right-shift your register.   
   > If it is even, replace "x" with "(x << 1) + x".  That's just some simple   
   > logic - no DSP blocks involved.  If your register or your counter   
   > overflow, you've found an "interesting" number and can pass that out to   
   > a PC to test it fully.   
      
   It is even simpler than that - using the optimization of always   
   calculating (3*n+1)/2 is ideal for look-up tables.  If you have   
   six-bit LUTs, you divide your number into five-bit blocks and   
   set up your LUTs for generating (3*n+1+carry_in)/2 - five LUTs   
   for five result bits.  You then also need two LUTs for generating   
   the propagate and generate bits for the five-bit groups.   
      
   You can then generate group generate and propagate bits for three   
   five-bit groups with two LUTs (15 bits) and so on.  Three levels   
   of P and G would give you 135 bits, more than enough.   
      
   The comparators could be more expensive; if this is done with LUTs,   
   you could only compare three bits each.  Maybe this is better   
   with the DSP blocks, I don't know.   
      
   > There's lots of scope for both high-level work (the housekeeping and   
   > tracking of operations for each of your worker elements) and low-level   
   > work (getting the carry operations to work at high speed).   
      
   Yep.   
   --   
   This USENET posting was made without artificial intelligence,   
   artificial impertinence, artificial arrogance, artificial stupidity,   
   artificial flavorings or artificial colorants.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)