Well, I personally don't know any algorithm to convert a "large number in b inary format into any base n, with n being a prime number" that would be a good fit for FPGAs.
d at these operations. But that skip method seems to be very promising... but it may need a lot of investigation/exploration/analysis/research from my point of view....But I really can see that the gain in skipping values is really major, I simply cannot think right now in a good "architecture" to implemented it!
What I can show you is where FPGAs shine. I wrote a module in Verilog code that can be synthesizable at 100 MHz (barely!) for a Zynq 7020 when retimin g is used (basically I did not pipelined the design, but used some of the t ools options that tries to do it for me) and that makes use of around 2100 LUTS.
The concept idea for the system would be the following:
There would be an application running in an PC (written in C, C#, Python, w hatever language it would be preferred) that would create jobs to be distri buted to boards with FPGA devices (either through Ethernet, or simply throu gh UART). In a FPGA device it would exist at least one (Soft) processor con nected to many of these modules, to which those jobs are distributed. Thes e jobs would consist in 2 72-bit numbers, one at which the processing would start, another at which the processing would end. (The module requires tha t the Start Number would be converted to each n Base by the (Soft) Processo r before it starts processing).
The description of the module is the following:
For each base (2, 3, 5, 7, 11, 13, 17) there is a counter of that base, wh ich at every and each 1 clock cycle advances one unit. In pipeline and in p arallel with these counters there is a tree of adders ( well for base 2 the popcount module is used) to sum up all the "digits" values of that number for each base. To avoid adders with more than 7 bits, overflow flag is used whenever a sum does not fit in 7 bits. At one point every adder of each ba se n is compared with each other. If none overflowed, and if all have the s ame value then this is a relevant value, and outputs this signal.
The module that I designed is not finished, is a proof of concept, it may h ave bugs, but has been designed to show how to generate sequences A135127, A212222, A335839 and the next sequence of ?Integers whose sum of di gits in base b is the same for every prime b up to 17.? It can be found in:
formatting link
For the people that will look into the code, sorry for the lack of comments ? just wanted to try out some things. For instance, a counter with
72 bits running at 100MHz is not something that I have done in the past (fo r low end FPGAs), or tree adders with like 20 7-bit adders running at the s ame 100MHz? These would ideally be pipelined by hand, but I got awa y with the tools options, after inserting a few pipeline registers. The 100 MHz objective would be easier to achieve if less bits would be used? ?
One module like this would process 100M numbers per second, and for the A3
35839 sequence would process up to 4294899857375(base 10) in half a day (A m I doing the math correctly? 4294899857375 / 100000000
/3600/ 24 = 0.497
09!)
Don?t know why your target is 72-bits and above, but with less bit s (lets say 64-bits numbers) 100MHz would be better achievable, and in a 15
0? FPGA board, it would fit 12/15 of these modules.
Regards, Nelson