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.
One of the purposes of this blog is to document the progress of my summer research project, StringPedia. The project is funded by a research bursary from EPSRC and I am working under the supervision of Dr Raphael Clifford.
StringPedia is (as the name suggests) a wiki-based project. The idea is to collect together a variety of string-based pattern matching algorithms and analyse them. A wiki is being used in the hope that the project may grow enough to get other people involved. It also means no-one can complain if I don’t add their algorithm as they can do it themselves!
Job 1 has been to set up this blog and MediaWiki, which has proved relatively straight-forward. Onwards to something more technical now; I’m going to dive in and put together an implementation of the FFT-based algorithm for solving pattern matching with don’t cares. Better get to grips with FFTW first though…
This is the personal blog for Ben Smithers, though it will probably serve more as a portfolio than as a blog.
I will also be using it to document my progress of my summer research project.