The NTT is proving to be quite hard. Despite finding a handy looking library (Finite Transform Library), it’s been causing me a bit of a headache all day. The problem seems to be that, because all arithmetic is done modulo some prime, the calculated results are obviously modulo that prime. It seems that it should be possible to get round this, perhaps by picking some prime big enough, but no luck thus far.

On the plus side, the web hosts have been great again and the equations in the wiki are now being generated by LaTeX on the server and they look much nicer. Also, the streaming model stuff is looking very interesting so I look forward to getting onto that.

Plan for tomorrow: re-organise the existing implementations into a more usable form and begin to devise and run some tests. Followed by another look at this NTT…

Having spent the last few months pretty much just using Java, my C skills seemed a bit rusty. Nevertheless, two initial implementations now exist for the “exact pattern matching with don’t cares” problem, the naive version and the FFT-based one. FFTW was quite straightforward to use in the end.

I’m now just beginning to get a sense of the scope of this project — there’s so much to do it’s hard to know where I should focus next…I need to add details for these implementations, come up with some way of testing and benchmarking their speeds, investigate the Number Theoretic Transform and make a list of other problems to solve. It’s quite exciting but a little daunting too! Onwards and upwards I guess.