Feasibility of fast Collatz Engine in an FPGA

[Leslie_Green]

I was wondering about the feasibility of making a high speed “Collatz Engine” in an FPGA. This is effectively a massive binary number with a simple iterative function:

If the large positive integer is even then divide it by two, otherwise multiply it by 3 and add one.

Repeat until the result is equal to 1.

I am currently doing such iterations using a 6 core Xeon processor, details here: http://lesliegreen.byethost3.com/articles/evidence.zip

Starting from a 10 million (decimal) digit number takes around 40 hours to iterate down to 1. This is using the MPIR library to build up the 10 million+ digit integer arithmetic required. In around 6 weeks this computer will have produced a suitable result. Above and beyond that range the Xeon processor route is effectively exhausted.

Can I get a much faster solution using the custom hardware of an FPGA? I want to do such iterations beyond 100 million decimal digits.

I would think that a 200 million bit full adder is infeasible all in one go. The MPIR library stitches together 64 bit words to make that functionality, which is why it is so slow.

How large a full adder is possible? 10,000 bits? At some point presumably fan-out or something is going to limit the maximum possible size. The divide by two is a simple shift. The multiply by 3 is an add of itself to a left-shifted version of itself. Then there is the add one step.

I don’t have the skills to implement such a design myself, so I was hoping to interest a digital specialist in picking up the project, if it is feasible. I think it would make interesting bragging rights, especially for an Intel employee running on an eval board. FASTEST COLLATZ ENGINE award goes to Intel!

I have a video summary of the current background here: https://www.youtube.com/watch?v=3cTZA-6SexI

(At the time of the video I had only probed large numbers up to 1E37163. The published limit is now 6 million decimal digits.)

[RichardTanSY_Intel]

Hi,

Unfortunately, we do not provide forum support on design coding or development. You may need to discuss or work with your team on this.

[RichardTanSY_Intel]

With that, I will now transition this thread to community support. If you have a new question, feel free to open a new thread to get the support from Intel experts. Otherwise, the community users will continue to help you on this thread. Thank you.

Best Regards,

Richard Tan

p/s: If any answer from the community or Intel Support are helpful, please feel free to give best answer or rate 9/10 survey.