Brett's Pick this week provides a subset of the functionality of our Symbolic Math Toolbox, but doesn't require any tools besides core MATLAB!
In his introduction to his submission on variable precision integer arithmetic, John D'Errico wrote:
"Every once in a while, I've wanted to do arithmetic with large integers with magnitude exceeding that which can fit into MATLAB's standard data types. Since I don't have the symbolic toolbox, the simple solution was to write it in MATLAB." I don't know how "simple" his solution was to implement, but John created a new variable class (vpi) that is quite easy to use.
Actually, John's code is pretty impressive. Using his object class, one can easily manipulate very large integers--often larger than MATLAB is comfortable with. Consider:
a = 17^17
a = 8.2724e+020
class(a)
ans = double
try factor(a) catch ME disp(ME.message); disp('Not gonna do it...wouldn''t be prudent!') end
The maximum value of n allowed is 2^32. Not gonna do it...wouldn't be prudent!
b = vpi(17)
b = 17
class(b)
ans = vpi
b^17
ans = 827240261886336764177
factor(b^17)
ans =
1 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
The Symbolic Math Toolbox
If you need more, or faster, there's always the Symbolic Math Toolbox. John's VPI class deals only with scalar integers, whereas VPA (from our Toolbox) also supports floating point numbers; it can work with Pi, for instance. Also, it supports matrices and n-dim arrays of numbers, and allows you to combine symbolic and numeric variables in expressions like "1.2*x+3.4*y". Nonetheless, John has given us a nice tool for manipulating integers. I'm interested in hearing your comments on this. Let us know how this might play a role in your workflows.
Get
the MATLAB code
Published with MATLAB® 7.7
Hi Brett.
It looks like I need to put up a quick patch in my factor code. Somehow a factor of 1 slipped out of that code in your test case for factor. This last release was a fairly large one, so I’m not surprised that something minor slipped through.
Regardless, factoring of large integers is one of the things I’ve been playing with in some depth lately. There are some very pretty results I’ve learned, as I wander through the depths of Pollard’s rho, quadratic sieve algorithms, and beyond. It also points out how nicely these methods fit into a parallel processing scheme. They are very nicely distributable if you have multiple CPUs.
Another very pretty area of mathematics lies in quadratic residues, solving quadratic congruential equations, Pell equations, etc. All very pretty stuff, at least for a long time numerical animalist like me. (If there are specific tools that someone needs, I’m always willing to add something, at least if I can figure out how to write the code.)
What has amazed me as I’ve built these tools in only a relatively short time (at this point, I have about a man-month invested, but the tools have grown very substantially in that time) is how easily you can build a very serviceable suite of tools for such operations. Even more impressive is the fact that if one wanted to do so, similar tools for variable precision floating point arithmetic, or perhaps rational fractions, etc., would all be easy enough to build on top of such a basic tool.
Matlab never ceases to surprise me in the sheer power of what you can do.
John
Thanks, John. The 1 doesn’t really bother me–it’s easily ignored. But then, “fixing” it would be trivial.
Your code is impressive, and useful. Thanks again for sharing it.
Brett
Actually, is it possible that you tested this with the previous release? I had a bug like that in an earlier release, but it does not seem to be there when I just tried your example. The new release allows full arrays of vpi numbers too. This was the main thing I added in the current release.
>> factor(vpi(17)^17)
ans =
Columns 1 through 16
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
Columns 17 through 17
17
I believe I downloaded this on 2/19/09, John, so if you posted an update since then, my blog post doesn’t reflect it. Again, the 1 doesn’t bother me, but the support for full arrays–nice! Sounds like I should get the new version.
Brett