Now that we have a (hopefully) working big integer implementation we can go on, either to arbitrary floating point numbers or multiple precision rational numbers. The latter is slightly simpler(1), so let’s take that one first.
Needful Facts
- The average rational number consists of a numerator and a denominator.
- Both are signed.
- About 61% () of the denominators of two random rational numbers have a GCD of one[bib1], the rest needs some massage.
Constructor
Three points only, not that much and the second point is even reducible. But that makes the constructor quite simple:
function Bigrational(){ /* if(arguments.length == 2){ ... } else if(arguments.length == 1){ ... } else { */ this.num = new Bigrational(0); this.den = new Bigrational(1); this sign = this.num.sign; }
Note: If you do not like to write variable = new Bigrational()
every time you can skip the new
keyword with the following construct(or):
function SomeConstructor(){ var sc = this; if (!(sc instanceof SomeConstructor)) { return new SomeConstructor(arguments); } // ... }
But it does not safe much in our case.
I decided against automatic reduction in the constructor but your mileage may vary as the saying goes.
Constants
We also need some basic constants, like zero and one, infinity maybe and something to act like an error-flag which could be NaN for example.
one is simple because of so it shall be .
zero is still simple because of so it shall be .
infinity could be a problem. I have seen it implemented as but that might cause physical pain in some people, so the already implemented Infinity
of our Bigint implementation shall do.
Error Flag well, NaN
seems apt here.
Basics I
Normalizing
The fraction might not be in its irreducible form, so we need to be able to do it. We need two functions for it, one working on copy and one working on itself. The latter is needed because we do not do automatic reducing in the constructor.
Algorithm 1: Reduce a fraction
- Input
- Output
- If a = 0
- return
- If b = 0
- return
NaN
- return
- If b = 1
- return
- gcd ← gcd(ax,by)
- a ←
- a ←
- return
The algorithm is the same for in-place and on-copy work, sans the returns, of course.
I/O aka. Read/Write
The Bigint implementation has the necessary things already implemented for String handling, we can use them. Just split the string at the delimiter “/” and set the signs accordingly. Some checks and balances are necessary but get skipped shamelessly in this description.
The ECMAScript number is an IEEE-754 double precision number. At least it should be according to the standards. If we assume that all engines are standard conforming—I think we should let the laughter subside a little before we go on, thank you very much—we can do the following:
Number.prototype.toBigrational = function() { var num, den, fp, ep, xp, i; if (this.isInt()) { fp = new Bigrational(this, 1); fp.sign = fp.num.sign; return fp; } xp = this.frexp(); fp = xp[0]; ep = xp[1]; for (i = 0; i < 300 && fp != Math.floor(fp); i++) { fp *= 2.0; ep--; } num = fp.toBigint(); den = new Bigint(1); den.lShiftInplace(Math.abs(ep)); if (ep > 0) { num.lShiftInplace(Math.abs(ep)); den = new Bigint(1); } fp = new Bigrational(num, den); fp.sign = fp.num.sign; return fp; };
The function frexp
is the same as the Lib-C function: it splits a double precision IEEE-754 number into its components: the fraction part and the de-biased exponent. I had it here one time but it was implemented using code from SunPro. To avoid any problems with licenses here I decided to implement it from scratch. Wasn’t that much work, I have to admit, should have done it right in the first place 😉
Number.prototype.frexp = function() { var fp, exp, dv, high, low, temp, hw, lw; if (this.isBigEndian()) { return [Number.NaN, Number.NaN]; } // If you want to exchange the DataView with direct access // to the typed arrays be aware that the typed arrays have // a big endian layout but the DataView has a little endian // one. dv = new DataView(new ArrayBuffer(8)); dv.setFloat64(0, this); // get high word high = dv.getUint32(0); // get low word low = dv.getUint32(4); // get IEEE-754 double exponent bits // mask is 0x7ff00000 because of the sign bit at 0x80000000 exp = ((high & 0x7ff00000) >>> 20); // handle special cases first if (exp == 0) { // strip sign bit from high word and if both together // are zero the number itself is zero, too; if ((0x7fffffff & high) | low == 0) { fp = dv.getFloat64(0); exp = 0; } else { // subnormal (denormal) numbers // expand. exact power does not matter much but // must be >53 temp = this * Math.pow(2, 100); dv.setFloat64(0, temp); // get the new exponent high = dv.getUint32(0); exp = ((high & 0x7ff00000) >>> 20); // correct exponent exp = exp - (1022 + 100); } } else if (exp == 0x7ff) { // infinity or NaN return [this, 0x7ff]; } else { // normal, just de-bias exponent exp = exp - 1022; } // set exponent of fraction part to bias but keep sign bit high = (high & 0x800fffff) | 0x3fe00000; dv.setUint32(0, high); fp = dv.getFloat64(0); return [fp, exp]; };
It is unknown how the engine handles endianess, so I checked it here explicitly with the following little script
// makes no use of the Number object, alternatively // Number.isBigEndian = function(){...}; Number.prototype.isBigEndian = function() { var buffer = new ArrayBuffer(8); var i32 = new Int32Array(buffer); var ui8 = new Uint8Array(buffer); i32[0] = 0xff; // byte 0 1 2 3 // little endian = ff 00 00 00 // big endian = 00 00 00 ff if (ui8[3] === 0xff && ui8[0] === 0) { return true; } return false; };
It seems to be made more clear in the next ECMAScript-standard but I doubt it before I see it.
It might be useful to split the integer from the fraction part of a fraction.
Algorithm 2: Split a fraction into an integer and a fractional part
- Input
- Output
- A ←
- B ←
- a ← A
- x ← B
- return
Comparing two fractions can get very expensive
Algorithm 3: Comparing two fractions
- Input
- Output
- If
- return -1
- If
- return 1
- If A = 0
- If B = 0
- return 0
- If
- return -1
- If B = 0
- If B = 0
- If
- return 1
- Else
- return -1
- If
- /* length in limbs */
- /* length in limbs */
- /* length in limbs */
- /* length in limbs */
- /* num. 1^{st} + den. 2^{nd} */
- /* num. 2^{nd} + den. 1^{st} *
- If
- If
- return -1
- Else
- return 1
- If
- If
- If
- return 1
- Else
- return -1
- If
- /* bigint p1.cmp(p2) */
- If
- If
- return -1
- Else
- return 1
- If
- return
One optimization would be to use the number of bits instead of the number of limbs in steps 5–8.
Rounding
Despite of the nature of the rational numbers to be always exact some mathematical operations can give rise to irrational numbers which are—the name suggests it—not rational, we need to cut them of at some point.
Out there in the jungle are also quite nasty beasts of functions which cause the fractions to blow up very rapidly. But even this horrible kind can be tamed with some rounding in between.
For the theory behind it see [bib3] and probably all of the other articles cited at the end but for the impatient I’ll give a short summary.
The method called median rounding seeks the rational nearest to the exact result given a certain number of bits to do so. That means that we need two fractions, one to the left and one to the right which we take and find out which one sits nearer to the target point. We do that by way of continued fractions.
To build a continued fraction out of a fraction
function rationalToContinuedFraction(numerator,denominator){ var p = numerator; var q = denominator; var n = 0;var temp; var ret = []; while(q){ n = Math.floor(p/q); ret.push(n); temp = q; q = p - (q*n); p = temp; } return ret; }
To build all fractions out of a continued fraction (small numbers only, to keep it legible)
function convergents(cf){ var r = 0;var s = 1;var p = 1;var q = 0; var ret = []; for(var i=0;i<cf.length;i++){ var tempr = p; var temps = q; p = cf[i]*p+r; q = cf[i]*q+s; ret.push([p,q]) r=tempr;s=temps; } return ret; }
Give it a try
var n = 12345678; var d = 987654321; console.log(n+"/"+d); var cf = rationalToContinuedFraction(n,d); console.log(cf.join(",")); var fracts = convergents(cf); console.log(fracts.join("|"));
Gives
"12345678/987654321" "0,80,152415,1,3,2" "0,1|1,80|152415,12193201|152416,12193281|609663,48773044|1371742,109739369"
We could do the whole CF first, do the whole convergents second, pick the two neighbours and find out which one comes closest but, as you might have guessed, we don’t do that, we can do the whole thing at once. Well, actually not, but we don’t need do do the whole thing so it is faster.
Algorithm 4: Median Rounding
- Input
- Output rounded to bits
- If
- Return
- If
- Return
- Loop
- If
- Break
- If
- EndLoop
- If
- return
- Else
- return
The algorithm works in-place, the actual JavaScript code works on copy. Both versions will have their uses.
Bigrational.prototype.round = function(prec) { var num = this.num.copy(); var den = this.den.copy(); var cf,median,num0, den0, num1, den1, den2, lf, uf,t1,t2,bprec; // TODO: checks & balances // first shortcut: we don't treat integers if(this.isInt()){ return this.copy(); } // the precision is given in bits, we make a number out of it // this is the number that gets compared to the denominator // from now on bprec = new Bigint(1); bprec.lShiftInplace(prec); // second short cut if the actual denominator is already lower // Yes, that means raising precision, like in floating point // numbers is not possible but also not needed at all. if(this.den.cmp(bprec) != MP_GT){ return this.copy(); } // initialize the two convergents num0 = new Bigint(0); den0 = new Bigint(1); num1 = new Bigint(1); den1 = new Bigint(0); while(true){ // continued fraction entry cf = num.div(den); // denominator of convergent den2 = den0.add(cf.mul(den1)); // we have the second point if(den2.cmp(bprec) == MP_GT){ break; } // a bit of shuffling around // TODO: increase legibility t1 = num0; num0 = num1; den0 = den1; // numerator of convergent num1 = t1.add(cf.mul(num1)); den1 = den2; t2 = num; // build new fraction for cf num = den; den = t2.sub(cf.mul(den)); } // check neighbourhood and take the nearest to exact result // Build a new denominator: the median. median = bprec.sub(den0).div(den1); // build lower fraction lf = (new Bigrational(num0.add( num1.mul(median) ), den0.add( den1.mul(median) ))).reduce(); // upper fraction is the last convergent uf = (new Bigrational(num1, den1)).reduce(); // compute the differences to the original and take the // one with the smaller distance. if(uf.sub(this).abs().cmp( lf.sub(this).abs()) != MP_GT ){ return uf; } else { return lf; } };
Some optimizations are possible but it is sometimes more useful to use a more exact result than necessary. We can skip the calculation of the precision as a number and use a bitcount instead. We are not able to do the last round anymore but we can just stop at a better, more exact convergent than necessary and use that instead.
The place to fish for it is at the very first two lines of the loop, where cf
is the numerator and den2
is the denominator of the convergent seeked for. If we take the fraction from the example above and place some logging there we nearly get the expected convergents. With 2^{23} as the precision:
"cf = 0, den2 = 1" "cf = 80, den2 = 80" "cf = 152415, den2 = 12193201"
Because of the zero at the start and the rather complicated shuffling we don’t get the expected 1/80 (0.0125) but we get the next 152415/12193201 (~0.01249999897483851861377500461) and because of the well chosen limit we break out of the loop here and don’t come to the final 1371742/109739369 (~0.01249999897484375001281445313) which is the reduced form of 12345678/987654321.
Yes? Really?
No, that was just by chance(2) the convergents are in the variables annotated as such in the code above. The denominator is indeed in den2
but the numerator for that fraction is in num1
which gets build much later. Yes, right below of the comment saying “numerator of convergent”. A place that wasn’t reached at all because the loop ended much earlier. You might try 123456789101112/987654321123456 with a limit of 2^{30} and some well placed logging to see the two convergents build up.
Algorithm 5: A Rougher Rounding
- Input
- Output roughly rounded to bits
- If
- Return
- If
- Return
- Loop
- If
- Break
- If
- EndLoop
- return
One little thing I forgot to mention which can help: the even numbered convergents are smaller than the exact number while the odd numbered ones are larger. This might be of little use but there is one very expensive division in the loop!
There is also one general caveat for continued fractions: the terms can get very large sometimes if we read from a decimal representation of the number, most (in)famous for it is probably the Champernowne constant. But these are rare and do not come up at all for rational input.
Basics II
Addition & Subtraction
Addition is, like in floating point arithmetic, the most complicated algorithm of the basic arithmetics but still simple. The algorithm is the one proposed in D. Knuth’s TAoCP [bib11]. The operation denotes the places wheere you can choose between addition and subtraction, the algorithm is the same otherwise.
Algorithm 6: Addition/Subtraction
- Input
- Output
- If
- Return
- If
- Return
- Return
The shortcuts are also nearly the same, just change the sign in case of subtraction:
- If
- Return
- If
- Return
Multiplication
Multiplication is quite simple. The early computation of the GCD is due to the good arguments of D. Knuth in [bib11].
Algorithm 7: Multiplication
- Input
- Output
- If
- Return
- If
- Return
- Return
You do not have to go the long way for squaring, just square numerator and denominator and call it a day. This assumes that the fraction has been normalized before so numerator and denominator are co-prime.
Division
Funnily, division is probably the simplest of the algorithms here.
Algorithm 8: Division
- Input
- Output
- Return
Elementary Functions
Elementary functions are the ones listed on the internet 😉
Joking aside, this post is already way too long. I will handle them—including the not-forgotten power—in my next post.
Footnotes
(1) the distance that the adjective “slightly” describes is in this case really, really, short.
(2) actually a longer trial&error to find something looking innocent enough 😉
Bibliography:
I found all english articles and books on the net. YMMV but I doubt it.
[bib1] G. Lejeune Dirichlet, Abhandluneg Königl. Preuß. Akad. Wiss., 1849, 69—83
[bib2] Matula, David W. Fixed-slash and floating-slash rational arithmetic Computer Arithmetic (ARITH), 1975 IEEE 3rd Symposium on. IEEE, 1975
[bib3] Matula, David W., and Peter Kornerup. A feasibility analysis of binary fixed-slash and floating-slash number systems Computer Arithmetic (ARITH), 1978 IEEE 4th Symposium on. IEEE, 1978
[bib4] Kornerup, Peter, and David W. Matula. An integrated rational arithmetic unit Computer Arithmetic (ARITH), 1981 IEEE 5th Symposium on. IEEE, 1981
[bib5] Hwang, Kai, and T. P. Chang. An interleaved rational/radix arithmetic system for high-precision computations Computer Arithmetic (ARITH), 1978 IEEE 4th Symposium on. IEEE, 1978
[bib6] Khovanskii, Alexey Nikolaevitch. The application of continued fractions and their generalizations to problems in approximation theory Groningen, The Netherlands: P. Noordhoff, 1963
[bib7] Gosper, Ralph W. Continued fraction arithmetic HAKMEM Item 101B, MIT Artificial Intelligence Memo 239 (1972)
[bib8] Vuillemin, Jean E. Exact real computer arithmetic with continued fractions Computers, IEEE Transactions on 39.8 (1990): 1087-1105.
[bib8] Flajolet, Philippe, and Brigitte Vallée Continued fractions, comparison algorithms, and fine structure constants Constructive, Experimental, and Nonlinear Analysis 27 (2000): 53-82
[bib9] Lester, David. Effective continued fractions Computer Arithmetic, IEEE Symposium on. IEEE Computer Society, 2001
[bib10] Seidensticker, Robert B. Continued fractions for high-speed and high-accuracy computer arithmetic Computer Arithmetic (ARITH), 1983 IEEE 6th Symposium on. IEEE, 1983.
[bib11]Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms, The. Addison-Wesley Professional, 2014.
Your site has some pretty interesting stuff. On the subject of arbitrary precision, I would like to point you to my mathematical/programming blog:
http://www.chaitanyavarier.com
As I have published a post about a Java Big Integer calculator I recently developed, which might be of interest to you.
The download you offer is just a binary blob. It is your decision if you do not want to publish your sources but you do not even describe you algorithms, just a bit of bragging (which I’m also OK with, you don’t have to be too restrained if you made something good!).
So if you do not want to publish your source (github.org for example is quite easy to set up. Even somebody like me was able to do it 😉 ) or at least describe the algorithms in such a way that anybody can write a program with the same functionality themselves I will most probably see your comment as spam and will act accordingly.
OK, took the time to decompile it. It is an explicitly proprietary program to do some factorial calculations without any fancy algorithms at all. That means that your comment is meant as a free advertising for your program. I cannot allow that. Please send me your address such that I can send you my bill for this advertising because only Automattic Inc. (the company that runs WordPress) is allowed to do free advertising at my blog.
Hi, thanks for your reply. I am actually going to be writing a post pretty soon describing the algorithms in my calculator, however I will not be releasing the entire source code for open viewing or reuse, as I do consider it a proprietary application as you mentioned. I have worked very hard on it, and I would not like people to decompile the application, as I may plan to sell it in the future. I have taken necessary precautions to discouraging users from decompiling the application such as obfuscation. I do appreciate the fact that you took the time to download it. However that being said, I do not appreciate that you have decompiled it, and I have strictly mentioned in the EULA that doing so would void the license agreement.
In regards to your statement on advertisement, I intended this no way whatsoever as a means of advertising my application, but more of a way to gain connections and exchange knowledge. That being said, I am a young developer still in pre-university, and I would appreciate if you took that into consideration as well. I will not be paying for what you consider to be advertising, as you haven’t mentioned any such policy on your website, nor is there one on WordPress.
If you are still interested in the algorithms and the mathematics behind the application, I kindly invite you to stay tuned for my next post on my blog, where I will be sharing code snippets featuring the basic algorithms and explaining how they work.
A replay? So you’re not one of these automated thingies? Good, but I didn’t expect it. I thought the comment has been posted by a spambot.
Many people, like me for example, are way more interested in the algorithms than in the actual implementations but the source might help sometimes if the description of the algorithm is too ambiguous. That is the case in some of the older papers which were length restricted because they were real dead-tree-type papers. The main problem with those older papers: the accompanying code was written in Fortran, Ada, or Algol too name just a view 😉
I do not run binaries from untrusted sources and I was on a computer that is too weak to run a virtual machine, so I had to decompile it which is quite easy with Java. But I will give it a try tomorrow when I’m on my new machine. (There are a lot of first person nominative singular pronouns here, I hope I don’t come over as egotistical as it looks?)
About the idea to sell it: who do you think might need such a program, who is the target? It is very difficult to sell software these days, the time of the little needful shareware for a buck or two is long over.
Well, actually, it is not over. These little shareware programs for a buck or two are now named apps. Problems: you need to get into the marketplaces (Apple, Google and maybe Microsoft) and it it is quite costly to do so, in money (e.g.: Apple) and/or work (e.g.: tens of different versions of Android) and/or luck (e.g.: Apple might think your little program is not worthwhile for some more or less unknown reasons).
I know, I tried it once. It is doable, but it needs a lot of work and patience.
Well, no, you didn’t and I hope you did not pay for the obfuscater. Some of these work to some larger extend but those are expensive and do a lot to your code and may even break it, so decompile it yourself and look what the obfuscater did to your code. It is also a good idea to use a decompiler with Java to see what the Java-compiler did to your code. It is not always what you expected it would do.
And at the end it will still be possible to find out what your program does, it just takes more time (and/or money) to do so.
You also cannot hide that you used an obfuscater.
I will not publish the result and will not even comment on it now.
You did see that I published code and mathematics to compute factorials/primorials etc. in two different languages (JavaScript and C) together with the necessary optimized Biginteger library (from scratch in the case of Javascript; I used LibTomMath in the case of C) with a lot of algorithmic optimizations? You can do the factorial of one million in JavaScript in a couple of minutes on a decent computer with this code (output in decimal lasts longer, it is not yet optimized).
(Yes, I, too, can brag 🙂 )
So why are you angry that I took your program apart?
I did not read the EULA. I couldn’t because I did not run your program. If you want people to read it you need to put it between the link to the download and the download itself as most sites do these days even when it is a Free License (Upper-case used intentionally).
The people still won’t read it but you are on a legally safer side with this method.
I really thought your comment was made by a spambot but I was not 100% sure so I was a bit provocative. Maybe a bit too provocative but it definitely woke you up, huh? 😉
And btw: if I would have considered you comment to be spam I would have deleted it without any further ado.
So you want to go into business with software? Be warned by me and my experience: software business is international, more than ever. That means that you will get confronted with a large, a very large number of different, sometimes very different jurisdictions.
For example: I live in Germany where it is completely legal to decompile your code for personal purposes, no matter what you write in your EULA for several reasons. The main reason in your case: your EULA is in English.
Found somebody to translate it? May still not work because some wording might make parts of it void; or even all of it in the worst case! That means you need a german lawyer to write a legally valid EULA for Germany. Rinse and repeat for every other language and/or jurisdiction. BTW: some nations have several official languages and you have to do it for all of them. This alone will cost a lot of money but if you have a working prototype and/or a good plan you might get some at Kickstart/Indiegogo etc.
I already know how you did it, but, yes, I will read what you’re going to write about it. And maybe even comment on it. You have read the subtitle of this blog? 😉
Hi again, and thanks for your reassurance. I completely understand your concern with people posting spam on your blog as it is a fairly prevalent issue (I believe most bloggers face it on a regular basis, and yeah Akismet can produce false positives). Actually the reason why my comment may have seemed to appear out of the blue is because I am new to the blogging scene, let alone the software development scene (this is my 2nd year since I’ve really committed myself to learning how to code) and I am currently trying to reach out to other like-minded people like you. Just from skimming through a few of your articles, you came across to me as a very experienced software developer/computer scientist, which I’m sure you certainly are! 🙂
I completely understand where you are coming from. However, I thought that people in general might like to first try the application and see how it performs before getting to the nitty gritty and analyzing the source code. To me it seems more logical, as most of the time it would be harder to find a bug in the actual code itself instead of running the application and experiencing the bugs. I guess to each his own (To Each His Own Array that is, although sadly no one says that :D). Anyways, I myself would be wary and suspicious of downloading binaries and executables from sources I did not really trust, so I follow your rationale.
Really? You were able to decompile the code, analyze it and refactor it in such a way that you could understand it perfectly? Wow I am baffled you could do it so quickly. Actually I did use an obfuscator called ProGuard, and it is completely free. I even decompiled it myself with the free JAD (Java Decompiler) to check that it had actually obfuscated the source, and it seemed pretty effective to me. Surely you’d have a hard time going through all the classes named a, b, c, etc? How could you tell which function did what? I’m curious, please do inform me of the process you went through!
Now that you’ve actually seen the code for yourself, and that
,
please don’t expect anything too great out of it, as my BigInteger functions (which I built from scratch) cannot match any official BigInteger library. If you’re saying you developed a BigInteger library yourself that can calculate the factorial of one million in a couple of minutes, then hats off to you! I think that is highly impressive! 🙂 I’ve only actually skimmed through a few articles in your blog as it is quite the library, but I will devote time to fully reading those articles which you mentioned.
Just to give you a heads up on what to expect, my factorial calculator will take a few hours minimum to calculate anything greater than 200000! (260000! took about 6 and a half hours on my 3 GHz quad core Intel CPU). But I’ll tell you that when it did return the answer, I crossed checked it with other sources, namely Wolfram Alpha. Thankfully I found out that the answer was correct indeed! It was a truly exciting experience. 🙂
Excellent question. Actually I was thinking that mathematicians and other programmers or people trying to cross check their answers or needing to calculate big exponents, factorials and prime factorizations would find it useful. Now I’m not so sure whether that’s valid anymore, as there are certainly free alternatives, and perhaps faster (free) ones :/. Well actually the idea was to keep it free for a while and gather opinions from programmers and mathematicians like you sir, and then decide what to do with it. So now the question is, do you think it is useful/practical for the audience I have described, and would you buy it if you needed it? I encourage you to be full on honest here, if you think it is not very useful, then I will immediately stop wasting any more time on it, and keep it as a personal achievement and a learning experience.
OK I will admit I was pretty ticked off at the fact that somebody was already trying to decompile my app just after having released. Again, I’m sure you realize now, how much sweat, time and frustration went into this. But now that you’ve given me some context, and informed about the international law issue, I understand. Actually I was aware of the German law regarding decompilation of source code, and I do understand that in order to fully protect your software, you must have a EULA for every country you will give access to. Honestly, it is not worth going to that much trouble in my case and getting it translated to multiple languages.
You certainly did! 😄 Yeah I did realize that you really couldn’t make me pay for that, but better to play it safe!
Anyways I must sign off here, as this reply is really too long already. I must say though, I really do appreciate your time, and your willingness to help out a budding software engineer!
Ooh, I forgot to mention on the subject of apps, I actually have developed my own Android app before (you can check that out too if you’re curious, just ask me for a link) and am doing some Android development currently as well. Porting PowArray to Android would be fairly easy for me.
Hi,
Ah, OK, I see. There’s nothing wrong with making errors when someone starts something new despite of the different opinion of many people who seemingly forgot that they did the very same themselves when they started.
It is completely OK to come out of the blue and comment on a blog entry that was not the problem. The things that made your first comment suspicious of being simple spam were:
You app is about factorials and I have several posts about factorials, why didn’t you comment there?
You really know how to schmooze a grumpy old man!
(Not that I would take it serious at all 😉 )
It depends. Finding bugs related to memory is sometimes simpler at runtime. Finding bugs in the GUI is of course simpler at runtime if you can see the GUI; but for a blind programmer the source is a better…ehm…source.
Then there are the bugs that depend on the environment of the user.
Then there are the so called Heisenbugs.
And many in between.
*sigh*
Perfectly? Hell, no! Of course not! Who do you think I…oh, you were sarcastic 😉
You program is small enough to find the essentials quickly (I don’t have to go through every single line of the GUI code for example). A complete analyse (going through every single line) would take about roughly 35–40 hours. At least that’s what I would bill for it 😉
And it is really nothing miraculous about it, just the many years of experience, that’s all. You will be able to that yourself in a couple of years, most probably even earlier.
What’s in a name? No, names do not matter and shall not matter. I found it often enough the case that the name of a function does reflect the function only at the beginning of the development and then diverges slowly from it.
The code itself.
OK, OK, I admit: a diagram of the flows is also very helpful 😉
The decompiler I used here was JD-GUI, it is quite comfortable. I made the flow-diagram with a pencil on a piece of scrap-paper (it’s really small if you ignore the GUI parts) but there are several good tools to do it automatically. You may take a look at this stackoverflow post that lists several programs and gives you keywords to ask Google for more (that post is from 2011, a lot has changed since).
First hit at Google was Visual-Paradigm which has a free trial. I haven’t tried it, just as an example.
Another one is jSonde which seems to build on jTracer which has been discontinued.
I have no need for automated tools besides a simple tracer (just the path from one function to another function(s)) if available and/or grep (always available) so I don’t know much about them.
Java’s BigInteger library (I mean Colin Plumb’s BigInteger.java. You’ll find it online, but beware: it is GPL’d!) is not very good from what I’ve seen. Not bad, far from it (they use optimal or near optimal algorithms) but also not highly optimized. A more optimized library should be able to do better without much effort or, if we look at it from the other side, it is not very complicated to build one with the same or at least nearly the same speed.
Most “official” BigInteger libraries like GMP are meant to give correct results and are not necessarily the fastest ones.
What I build was meant (and is still, I just don’t know how to find some time to work on it) for pedagogical use without being too slow and too simple. That means that I never (that’s a lie, of course 😉 ) used highly specialized optimizations based on architecture, user mood and cycle of the moon, just faster (BigO-wise) algorithms.
I hope the JavaScript version can do it in a couple of minutes, never actually tested it 🙂
But it is not very impressive, the algorithm has been invented by a much more prominent person I just implemented it.
You may take a look at all that stuff (and more) at my Github account (last commit in April *sigh*).
My Github account is more or less a scratchpad so don’t expect anything to be clean and tidy :$
The things I did to Tom St Denis’ LibTomMath are Public Domain as is LibTomMath itself, so you can use it freely, e.g.: in your program. LibTomMath is written in C but it has a very good description of the algorithms (not my stuff, but I’m working at the documentation) and useful pseudo-code. Even if you do not want the code itself you really should take a look at the documentation (PDF).
To be expected.
I’m envious.
Oh, yes, it is! And it never wears off! 🙂
The only thing that those people use is the same that you used: Mathematica. Especially since wolframalpha made it very simple to do so. Although they seem to restrict it more and more.
A free alternative to Mathematica (without all of the bells and whistles of Mathematica but still very useful) is Maxima which is build upon MacSyma a very prominent computer algebra system at that time.
Prime factorization gets done with special software, mostly sieves for larger numbers (larger than 34,155,071,728,321 to be exact) and special sieves for special numbers (e.g.: Mersenne primes).
Exponentiation depends on the numbers and exponents and if you want to do modular exponentiation. Everything is described well, with pseudo-code, in the documentation of LibTomMath I linked to above.
Oh, please! I really hope that was meant ironically otherwise I would be a bit…indignant about making me feel that old! 🙂
No, definitely not. At least not as it is. It must be either faster than wolframalpha or more useful.
I don’t buy specialized software for myself, I would write it myself and that’s what many if not most people would do, too.
But there is nothing wrong about giving it a try as long as the cost is neglible!
Don’t do that! Don’t tease me in such a way, for I might give you what you asked for! 😉
You can learn from it and I wouldn’t call learning a waste of time.
I know that very well.
But as I have tried to make clear: the chance to get anything out of a small app is very low. You can make a small amount of money (a couple of grands) with a good game together with a large amount of luck if it gets found by a prominent blogger and gets a positive review, too.
If you, please?
Yes, it should work easily for this kind of program.
That simplicity stops immediately if you want to do something more and interact with the OS or worse get information from the hardware (GPS, Hall-effect sensor etc.). That is generally the same everywhere except where it isn’t.
You could specialize on that, e.g.: offer some service to port software from one version of Android (changed by company XYZ to run on phone ABC with carrier IOP and contract version 123.321.a, LTE only) to another version of Android (changed by company XYZ to run on phone ABC with carrier IOP and contract version 123.321.b, LTE only).
Yes, it is really that bad, I don’t exagerate the situation very much.
This is also a nice place for Heisenbugs: there is a bug, repeatable by many but if you try it, it disapears and you wonder (well, actually, I’ll spit and curse, making an old midwife blush but your education is most probably better than mine) why. It is, in most cases, caused by a very slightly different version of the phone’s software that is nowhere noted.
It was the small difference between an argument taking an unsigned char (documentation) and a signed char in the actual implementation that made me give up doing it myself and to outsource it to people who know such details in and out. They took a lot of money, hence my suggestion to specialize in it.
Or write a library that does it. I’m pretty sure that you can sell it if it gets updates regularly. It’s a lot of work, though.
But it’s a thing I would pay some money for if I would need it. “Hassle-free” is a very good argument to press money out of people like me 🙂
PS: I just saw that I used “replay” instead of “reply” in my first answer, so if you find some bad grammar/choice of words feel free to tell me, I’d appreciate it. One of my reasons to start this blog was to get better with my English but that doesn’t work very well with no feedback at all. That assumes that you are a native speaker and if you are not I’m envious again! 😉
Hello again,
Yeah I do realize I could’ve been more careful about it, but as I’m sure you’ve come to realize, I was tremendously excited about finally having a Java Arbitrary Precision calculator app that was polished enough for me to call it “ready for release,” and I simply wanted to get as many opinions as possible from others whom I thought would be interested.
I did a quick search in WordPress for terms like “algorithm, “arbitrary precision” and even “Big Integer.” Unfortunately I wasn’t able to find too many programming blogs on WordPress which I thought would be related to mine, but I persisted a little and, lo and behold, I found yours. You can guess what happened next, but as they say, there’s a first time for everything, right?
I understand, although if somebody presented me with an app they created, I would certainly want to see it working in real time first instead of doing it the other way around and spending a decent amount of time analyzing and reading the code, then saying “hey this is pretty well organized and high quality code! I bet this will run perfectly on my rig!,” and then finding to your disappointment that it crashes upon startup. Of course this is exaggerated, but I think you will get the point.
I used JD-GUI as well to decompile my app to see how good of a job ProGuard did, and it seemed pretty well obfuscated to me! Actually you did emphasize on the factorial function, have you taken a look at my exponentiation and prime factorization algorithms? There’s a lot more to look out for there! Now on the subject of obfuscators, which one would you personally recommend, as you seem to be telling me that ProGuard didn’t cut it out for me :D!
This passage seems a little ambiguous, were you referencing my app here? Of course, I haven’t bothered optimizing my app to achieve the prime efficiency and breakneck speeds it could have. A wise man once told me, optimizations are the root of all evil. I doubt whether this is really true, but I have experienced for myself how distracting it can be to want to eke out that extra percent or two of improvement in performance. I actually have tried to make my algorithms faster by implementing simple, “common sense” type optimizations, and have achieved maybe a 30% increase in speed overall since my initial build. I did manage to make the app less of a memory hog though (it use to consume over 1 GB RAM for million digit calculations, now it’s under 200 MB).
One thing to note is that I have not yet had formal training in computer science, nor has anyone taught me how to program (I’m still pre-university), so my knowledge of Big-O notation is limited. But yes, I do understand the basics, I guess I just need to find time to do everything nowadays with school and everything in the way!
Really? Your CPU is still a quad core, and 3.9 GHz at that! Of course Intel is known in general for less stability issues and better performance per core, but it still seems to be a solid CPU!
The only thing is you need an internet connection to use Wolfram Alpha as it performs the calculations on their supercomputers. Also there are limitations implies such as limited computation time. Actually I tried to use it to check my answer for the sum of the digits in 260000! and it wouldn’t give me an answer. Also Mathematica costs around $149 per year, which of course isn’t unreasonable if you’ll use it on a regular basis. I haven’t really looked into the free alternatives, but I’m sure there are some fast and free Arbitrary Precision calculators out there. Although the thing is, I haven’t been able to find a good one for Android, offering the same functionality as mine. So I still think there is some potential for selling my app or at least distributing it for free and it being useful to others.
I understand the deal with sieves, although believe it or not, my calculator can return return the prime factorizations of numbers up to 2^63-1 which is about 9.223 quintillion. It can do it pretty fast as well. It can find the prime factorization of 2^63-1 (quite composite) in about 8 ms. However large primes will obviously take more time. The longest calculations have taken 18-20 seconds on my CPU, and they’ve been primes.
Well the thing is, I try to address others with as much respect as possible, so I do apologize if it bothered you.
Well currently there is a slim chance with my experience and knowledge coming up with something faster than Wolfram Alpha, but what exactly do you mean by more useful? I mean as far as functionality goes, what would would you think I could add to it to make it useful enough?
Oh by the way, did you actually get a chance to test the app on your other machine? What did you think of the GUI, and the other functions? I would appreciate if you could take a look at all the features including the preferences box (it should take no more than 10 minutes).
Sure here’s a link: https://play.google.com/store/apps/details?id=com.ChaitanyaVarier.FitnessBuddy2Go&hl=en
Thanks for the idea, I’ll consider doing it eventually when I have the time.
Your English is very good, and I am indeed a native English speaker, although I can relate, as I also must know French as a second language. Since you asked for it, I might be able to help you out on that from time to time! 🙂
Now that I notice your tagline, did you mean to write “rancid” instead of “ranced?” Also I have a moderate case of arachnophobia, but that is one fine looking arachnid! Very ornate and mesmerizing!
Hi,
As said before: it depends on the program, including its size, the author, and my ability to sandbox, but: yes, I would look at the source first and run it only if I like what I saw. I won’t go to such a length if it is from a trusted repository (e.g.: Debian, OpenBSD and similar).
And if it crashes on start-up: well, than there’s a bug to find and the real fun begins! 🙂
Yes.
But I cannot discuss it publicly as long as your license forbids it, so please go on with your description of the algorithm(s) such that I can know what you want to be publicly known and what not.
Well, that sounds a bit harsher than I wanted it to be, sorry. One prejudice of Germans which is correct: we can be quite blunt without recognizing it.
A main disadvantage of closed sources and highly restricted licenses is that nobody is legally able to tell you publicly what you did wrong, or could be done better, is a security risk (but that’s a thing I would publish without much hesitation or warning) or just suffers from a lack of elegance.
One more argument: you, as a young ambitious programmer with something new will gain more from publishing a paper with accompanying example code (or even without, doesn’t matter much) in a well respected journal than trying to sell the program. You will have a very high chance to get accepted at an elite university, maybe even the MIT or the RWTH Aachen (Ow, c’mon, a bit of patriotism is allowed, isn’t it? 😉 ).
None.
All of these tools suffer from one very basic problem: given enough time and/or money they can be defeated.
Time is available in vast abundance because of the many able people having an Internet connection. You will also fail if you bet on the money part. You think, no, you are even sure that it needs a large laboratory with tools worth millions of bucks? Like Microsoft thought with their X-Box? When a student working in his laboratory was able to crack it in a couple of days? OK, it was not his laboratory but the laboratory of his university and yes, it had the million dollar equipment in it!
So, obfuscate it with a strong one if your investor wants it or for watermarking (one of the uses of an obfuscater that is actually useful), otherwise safe your money.
I once found an article about it, but where did I put it…ah, here it is. It should give a deeper understanding about the pros and cons of obfuscation.
It has lots of links and examples, really lots of links and examples, a good read for a long weekend 😉
Yepp, know that guy. Does he still collect photos of curious street-signs?
(I think it was “Premature optimizations…” but I may err here and am too lazy too look it up.)
I did not mean fine-tuning at the bit-level but at the Big-O level. Use good, robust, well know algorithms in your programs and if all runs well you might be able to squeeze another percent or two out of it. And because you already cited Don Knuth: his TAoCP is a very good source for such algorithms. Such a good source that is is a must for programmers to have (you don’t read it from front to end, you look things up there. Has anybody read it front to back except the editor?). It is quite expensive to buy but you’ll find electronic copies on the net if you do not have the money.
Examples? Examples. (you’ll find JavaScript code for all of it somewhere here on this blog but that code might be buggy, better look into my Github.org account for it)
Multiplication:
You do not need anything fancy-schmancy for a couple of hundred decimal digits.
For more than a couple of hundred decimal digits, say a couple of thousand digits you’ll use a Toom-Cook algorithm starting at T-C-3 which is also known as the Karatsuba-algorithm and if you have even more you use some kind of DFT based algorithms. Don Knuth has even more, albeit only theoretical ones.
Factorial:
Very small factorials come from a precomputed list (I used the first 50 for JavaScript as far as I remember)
Small factorials get treated with the binary splitting algorithm (up to about 6,000 decimal digits for my JavaScript implementation) and for even larger factorials the Borwein algorithm gets used.
The non-naïve algorithms depend on the fast multiplication algorithms to be fast themselves!
Division:
For small divisions or if the difference between numerator and denominator is extreme you use the textbook long division you got taught in primary school. For larger numbers and normal ratios you should use the divide&conquer algorithm invented by Burnikel and Ziegler (the cut-off point is astonishingly small, just about the same as the Karatsuba cut-off point!), for larger, much larger numbers you can use an algorithm based on Barret division but I found the usable range between Barret division and Newton division (for all the rest of it) too small for the hassle to find the bug in my implementation of the Barret algorithm.
I implemented no further optimizations in the JavaScript version.
But I tried. Of course, I did! 😉
One of many points of optimization is at the level of the individual multiplications. ECMAScript (the industrial norm of JavaScript) has a 64-bit IEEE-double as the basis of all its numbers (this might change but I doubt it will happen in a short time) and I used not all of it, only 26 bits (the mantissa has 52 bits and hence is the size of the largest integer you can use in JavaScript). With a bit of bit-pushing you can use all 64 bits of the number and are able to use 32 bit large limbs. With even more bit-juggling you can use 64 bit long limbs but that is too much and will make it significantly slower.
JavaScript is just not made to get manipulated at the bit level (that sounds a bit dirty, doesn’t it? 😉 ).
Ah, nearly forgot it! I do have one of these more obscure optimizations implemented: the last steps of the FFT butterfly-tree get treated linearly and you can fine-tune the amount of linearity depending on the L1-cache size of your processor. That works quite well for the C-version, not so much for the JavaScript version but YMMV.
Nothing gets computed in parallel with the JavaScript implementation, although there is a chance in JavaScript to do it with so called Workers.
Paralellizing is a work in progress for LibTomMath, nothing published yet. Nothing is planned for LibTomFloat but there is much in it that would gain a lot from using multiple processors.
The 30% are not worth the hassle as long as you don’t get paid for it.
Better algorithms would increase operations with million decimal digits by several magnitudes.
1000000! * 1000001! (5565709 dec. dig. times 5565715 dec. dig.) can be done in about 1,5 seconds with PARI/GP (64-bit version with GMP 5.1.2 as the computing library, single threaded) and a stack size of 61.035 Mibytes, that means that at least your memory usage is OK. GMP uses very large limps and also several methods to safe memory, so 200 MB is not bad for a start.
I do not know how long textbook-multiplication would have needed but my bet is on “a couple of hours if not days” 😉
No excuse in the time of Google! 😉
Nope, that was mean, even with the smiley, sorry.
How is the wiki entry? Mmh, a bit too math-heavy for now? But if you scroll down you’ll find a table with some descriptions you might find helpful. At least as a rough overview over what is faster and what is slower. There are also some links at the end. Don’t worry if you do not understand it now, it is very complicated and you need to understand it only if you found a new algorithm and want to publish a paper.
Yepp, it was a cheap joke, I apologize. (The kernel downclocks (is that a word?) the cores if idle so I have only 1.9 GhZ showing up in the CPU info)
But the AMD-combo is quite nice and together with 8 gigs of RAM (1.5 of it for the GPU) it fits my usage very well.
Mathematica does not run on supercomputers, at least not out of the box and it doesn’t even need to, they (wolframalpha) work with a lot of individual instances in parallel on “cheap” off-the-shelf hardware.
If all you need is a well tested, robust arbitrary precision calculator I would suggest PARI/GP.
It calculated the sum of digits of 260,000! with the following, very naïve program
which I even shamelessly stole from Rosetta Code.
It took some time (9min, 5,941 ms to be exact and if you are a good additioner you most probably can do it faster by hand 😉 ) but the result is 5,538,510. PARI/GP has also a build-in function
sumdigits
which my version of PARI/GP doesn’t have? OK, compiled a newer version which has the function and it did it in 311ms (including the calculation of 260,000!) with the same result.Tried one more: sumdigit(1000000!) = 23903442 in 2,060 ms.
The algorithm they used:
Convert a number to a string base 10 (that’s quite fast, believe it or not, if done correctly with Schönhage’s algorithm)
Put the result into an array with nine decimal digit long limbs (as native integers, not as a string)
For each limb compute the digit sum and finally add all up.
The digit sum of a single limb gets computed with the help of a table such that we do not have to loop over every single decimal digit (the %10 from the PARI/GP line above) but can work with three decimal digits (%1000) at once.
But the normal way of finding the digit sum of a factorial is factoring it (very easy with a factorial as Legendre found out in 1808) and just sum the digits of the individual factors. You can do that all in normal precision (no actual calculation of the factorial needed at all) and the limit is the largest integer representable in normal precision. So if you use BigIntegers you can even compute the digit sum of gogol! ((10^100)!) with no problem in a couple of seconds, probably less.
BTW and I just squeeze it in here: if somebody wants to know nothing but the number of digits of a factorial you can use a log-gamma function, Java has one, as far as I know but it is easily done with just two terms of the Stirling series for factorials larger than 1!. In pseudo-code (but runs in PARI/GP as it is, too)
(The error is less than 1 but I spare you the proof)
And if you want the number of decimal digits: just divide by log(10) as usual. Don’t forget that !
If you like PARI/GP: it is available for Android, too, aptly named PariDroid (2.2 MB).
I didn’t even know that, thought I need to do it myself if I want one! Kudos to the folks at PARI/GP!
The page at the university of Bordeaux seems to lack a secure connection but a certificate costs money, I know *sigh*
Highly composite numbers are easy. Semiprimes, composites with only two factors, are more complicated especially if both factors are of the same size. You may give 4294967291 * 4294967279 = 18446743979220271189 a try, a 64 bit semiprime. Even PARI/GP needs 6 ms for it.
I would test larger numbers with a probabilistic test first (e.g.: Miller-Rabin) and check with a deterministic primality test (e.g.: the improved AKS test) after it if not composite. That should be faster on average. But only for larger numbers and only if the factorization algorithm is as slow as yours for this magnitude.
Just to show you how fast a sieve is: I took GP/PARI to the task of factoring the 39 decimal digits long semiprime 18446743979220271163 * 18446743979220271177 = 340282363434899324198938090248333168851. Done in 118ms with a qudratic sieve.
The 78 dec. dig. long semiprime 340282363434899324198938090248333168569 * 340282363434899324198938090248333168511 = 115792086864840908600172893069513192777415458041302086447660739797116045730759 seemed to be a bit large but got done in 14min, 31,005 ms with a number theoretical sieve.
That is very nice of you and I, as most other people appreciate that very much but you need to adapt to the environment from time to time.
Calling somebody “sir” sounds very curious in a comment to a normal blog post, to say the least. Many will take it as irony or even sarcasm, just as I did.
This advice is of course void in cultures with finer grained hierarchies, e.g. Japan or if you talk with a client etc.!
But it really irritates the people at normal blogs and forums if you call them Sir/Mam’.
There is also the problem of “On the internet nobody knows if you’re a dog!” (Peter Steiner, The New Yorker, July 5, 1993): you do not always know if you should call somebody a Sir or a Mam’ without asking them and not everyone is willing and/or able to tell you (you may read up about gender-fluidity if you don’t know what I mean). It might even change over time. More than once. In less than a day.
The English language allows to weasel out of the problem with the use of they/their etc. (I doubt I use it correctly but you should know how to do it properly) other languages don’t have it (e.g.: German) and there might even exist languages that have a special construct for it.
Uhm, I think I digressed a little bit here, did I not? 😉
Wolfram Alpha uses GMP for numerical computations (probably, can’t say for sure, of course but Mathematica 5.0 did) and it is possible (see for example APFloat) to write a faster one. Although not much faster and not everywhere.
GMP is a general purpose library and as such can be easily beaten in a special domain by a special program.
I don’t have the faintest idea. Everything your program does, other freely available software is able to do, too, and they do it faster and better (the chance that GMP gives a wrong result is near zero, I would even assume a hardware failure if that happens).
So you were using JDK-8?
One of the problems with Java and other JIT based languages (and several others, it’s a general problem): the compiler has to fit the interpreter. And it doesn’t matter if the interpreter is a JIT compiler or a processor. The cause of many grey hairs.
You may be able to set a lower level in your IDE. If you can do so, set is as low as possible (but not lower, of course 😉 ), that should solve it.
Yes, I could do it myself by decompiling and recompiling but, hey, it’s your bug! 😉
You still need a playstore account for free apps, too? *sigh*
My sister has one, I’ll ask her tomorrow.
But it looks good from the screenshots.
I would have made videos instead of stills for the descriptions (or are they already?) but can’t say more without running it (this is one of the examples where you have to run it because of the different environments of Android based phones and tablets but mainly to check the usability).
“Eh, do I have to actually use it?” he asked with a hint of panic in his voice, “I mean: doing sit-ups and all that stuff?”
BTW: what is a burpee and will I regret to have asked?
Canadian, if I’ve read it correctly?
One of the countries I haven’t visited yet, still want but probably never will.
I don’t speak French but I’m pretty sure that my harsh German accent lets me survive even Quebec with English only? 😉
Is it really that bad between the French and the English speaking parts of Canada?
I live near Belgium and visit it from time to time (they brew some very nice beer there 😉 ) and there it definitely is bad between the ca. 59% Flemish (they speak Dutch) and the ca. 41%Walloon (speaking French), there is also a small German speaking colony in the eastern part of Belgium but it’s a very small colony.
The Flemish region is the richer one.
That would be very nice!
Yepp, but I didn’t recognize the error until it was too late; the original picture is gone. Maybe hidden in one of the backups but I doubt it.
But you’re right, of course, I should correct it.
Araneus diadematus, very common here, so if I can’t find the original picture I should be able to do another one.
taking the liberty to answer myself:
Nope, doesn’t work. Well, it does work but I forgot that you need to over the whole entries for every new factor. That doesn’t make it as fast/slow as computing the actual factorial sans the factors of 10.
(might be faster for extrem large factorials, yes, larger than gogol! but I did not fully analyze the algorithm)
*grrr*
Sorry for that.
Hello again,
Sorry I couldn’t get back to you sooner, I was on a little vacation with family. Anyways, I’ve posted my first article regarding Project Euler problem # 16 with accompanying source code. My solution contains the original algorithm which formed the basis of my exponent calculator in PowArray. I will post about my factorial and prime factorization algorithms soon.
[blockquote]
Canadian, if I’ve read it correctly?
One of the countries I haven’t visited yet, still want but probably never will.
I don’t speak French but I’m pretty sure that my harsh German accent lets me survive even Quebec with English only? 😉
[/blockquote]
Absolutely, good guess! It is quite a nice country, very good biking paths here in Quebec. Montreal is a nice city for cycling among many other things. Unfortunately it is worse here in Quebec than in Belgium, as there is a significant francophone majority here (~80%).
[blcokquote]
That is very nice of you and I, as most other people appreciate that very much but you need to adapt to the environment from time to time.
Calling somebody “sir” sounds very curious in a comment to a normal blog post, to say the least. Many will take it as irony or even sarcasm, just as I did.
[/blockquote]
Again, I apologize for that. How would you prefer I address you?
[blockquote]
Yes.
But I cannot discuss it publicly as long as your license forbids it, so please go on with your description of the algorithm(s) such that I can know what you want to be publicly known and what not.
[/blockquote]
OK, you might like to check out my first post, as it discusses my exponentiation algorithm. Again, I have modified it quite a bit for my app, but the idea remains the same. Coming back to the discussion regarding open-source code, I have explicitly made a statement explaining that whatever code I post on my blog is open-source and free for use in personal projects, therefore I invite you to comment on anything I post! 🙂
[blockquote]
One more argument: you, as a young ambitious programmer with something new will gain more from publishing a paper with accompanying example code (or even without, doesn’t matter much) in a well respected journal than trying to sell the program. You will have a very high chance to get accepted at an elite university, maybe even the MIT or the RWTH Aachen (Ow, c’mon, a bit of patriotism is allowed, isn’t it? 😉 ).
[/blockquote]
That’s really encouraging advice! Someday I will try and see if my school research journal would publish one of my articles!
[blockquote]
A wise man once told me, optimizations are the root of all evil.
Yepp, know that guy. Does he still collect photos of curious street-signs?
(I think it was “Premature optimizations…” but I may err here and am too lazy too look it up.)
[/blockquote]
I don’t think we’re talking about the same guy, but that’s something that’s stuck with me.
[blockquote]
I did not mean fine-tuning at the bit-level but at the Big-O level. Use good, robust, well know algorithms in your programs and if all runs well you might be able to squeeze another percent or two out of it. And because you already cited Don Knuth: his TAoCP is a very good source for such algorithms. Such a good source that is is a must for programmers to have (you don’t read it from front to end, you look things up there. Has anybody read it front to back except the editor?). It is quite expensive to buy but you’ll find electronic copies on the net if you do not have the money.
No excuse in the time of Google! 😉
Nope, that was mean, even with the smiley, sorry.
How is the wiki entry? Mmh, a bit too math-heavy for now? But if you scroll down you’ll find a table with some descriptions you might find helpful. At least as a rough overview over what is faster and what is slower. There are also some links at the end. Don’t worry if you do not understand it now, it is very complicated and you need to understand it only if you found a new algorithm and want to publish a paper.
[/blockquote]
Yeah I did understand that, but the bit level is something I will tackle at one point. Actually what I meant by “limited knowledge” was that I know the basics, and about the other asymptotic growth notations, theta and omega. Actually runtime complexity is a field that has always captured my attention ever since I started programming, because I always wondered how I could make my programs faster and faster. Actually considering the fact that I love math, and don’t mind reading through some derivations, proofs, etc, the Wikipedia page is not all that bad.
By the way, thanks for all this information, it is kind of you to go through all this trouble. 🙂
Sum the digits of the individual factors? Do you mean get the prime factorization first and then sum the digits of the factors, or the regular factors? This is a surprising result, I’ll have to read up on this.
[blockquote]
Highly composite numbers are easy. Semiprimes, composites with only two factors, are more complicated especially if both factors are of the same size. You may give 4294967291 * 4294967279 = 18446743979220271189 a try, a 64 bit semiprime. Even PARI/GP needs 6 ms for it.
[/blockquote]
Nope, can’t do it, doesn’t fit the long datatype max value (263-1).
[blockquote]
I don’t have the faintest idea. Everything your program does, other freely available software is able to do, too, and they do it faster and better (the chance that GMP gives a wrong result is near zero, I would even assume a hardware failure if that happens).
[/blockquote]
OK, but the only question is, are any of them user friendly? Can you easily save the output to a file? Does the GUI lag when you try to scroll through the output after performing a very large calculation? Is there a small upper bound to the largest possible calculation? Sure, my algorithms are slow at the time being, but hey, what is to stop me from learning about effective optimizations I could implement, and perhaps implementing some better, well known algorithms? Coupled with my GUI, I think my algorithms form the basis for an app that is unique in that respect as it solves these problems.
[blockquote]
You may be able to set a lower level in your IDE. If you can do so, set is as low as possible (but not lower, of course 😉 ), that should solve it.
[/blockquote]
Why, are you unable to run Java 8? I would rather use the latest version of Java when developing, mainly to make sure I’m using up to date APIs, libraries, etc.
[blockquote]
I would have made videos instead of stills for the descriptions (or are they already?) but can’t say more without running it (this is one of the examples where you have to run it because of the different environments of Android based phones and tablets but mainly to check the usability).
“Eh, do I have to actually use it?” he asked with a hint of panic in his voice, “I mean: doing sit-ups and all that stuff?”
BTW: what is a burpee and will I regret to have asked?
[/blockquote]
I hope you eventually do get to see it in action! I am considering creating a short demonstration video for it, but since last summer, I haven’t released any updates for it, and downloads are currently stagnant. No, you do not have to use it, but you can give it a shot if you like! A burpee is a sequence consisting of a squat, a push-up and a jump. Quite a good exercise. 🙂
If I have missed any details in this post, I apologize as my fingers are practically falling off from typing all day!
Just realized, I misspelled a few blockquote tags, and some of those blockquotes didn’t render properly. Time for a break.
Wow a lot of stuff didn’t render there,
Also coming back to a few things you mentioned,
I don’t remember ever distinctly citing Don Knuth, but his work certainly interests me. I’ve developed an interest in googology over the past year, and I have to say, I find his up-arrow notation particularly convenient. Hyperoperations is also a topic that has interested me. Watching Numberphile videos and solving Project Euler problems is also what got me into the big numbers craze, and ever since I’ve wanted to develop something cool that could produce such big numbers, and hence PowArray came about. I’ve also gotten interested in recursive functions, namely Ackermann’s function which produces large incomprehensible numbers astonishingly fast.
On the subject of sieves, how fast is Eratosthenes’ sieve? How difficult is it to implement a quadratic sieve in an object-oriented language?
I believe the correct term is underclock, but mine does too. After all, you wouldn’t want your CPU running at full throttle all the time, would you?
OK, I really could do that, but I don’t consider it a bug. I mean, Java 8 was released over a year ago, so there’s been plenty of time for people to update. Also, is the Java update process really that painful?
I noticed that you allocated a maximum heap of 128 MB. This should be sufficient for maybe calculations in the range of a few hundred thousand digits. If you would like to try a calculation going into a million digits or more. (I doubt you would, but here it is anyway) I recommend at least 512 MB.
Hi,
No reason to be sorry, family comes first.
Again: don’t apologize; it is rarely a bad thing to be too polite but it might irritate. You’re new to this environment and do not know the details and because it is the duty of old farts like me to explain it, I did.
Oh, and for me it is: “either all titles or none” and I prefer none—first name is enough.
You don’t know my first name? Ask Flickr, they know 😉
I assume that you want me to discuss it on your blog, correct?
But one thing here: please link. Everything that you cite that is online should get linked and things that are only available in print should get a link to an online-bookstore (and don’t forget to get an affiliation with the company to get a dime or two if somebody buys that book via your link). It is sufficient to link the first time only.
And it was a very good idea to use well known licenses instead of baking your own!
Someday? Why not now?
The quote is by Prof. Donald Knuth and yes, he does collect pictures of curious road-signs.
You’ll regret that you told me that! 😉
And it is even kinder of you to patiently dig through the erratic rants of a grumpy ol’ man! 😉
Basically: yes, but I erred on this as I noted in a follow-up to my own comment. I thought I could get the digit sum without calculating the full factorial which is correct but I also thought that it would be much faster but that is very wrong. It is about as fast as the Borwein algorithm but I haven’t made a proper calculation of the complexity yet.
You’re using Java 8, don’t you?
It seems to have an unsigned version, too, now. Please try this (18446744073709551614 = 2^64-2):
How do you define “user friendly”?
That term is not as subjective as some prominent people might want to make you believe but sadly also not as objective as other prominent people might want to make you believe.
The simplest thing would be to describe it: what are the things you saw as problematic and how do you think you solved them. If you can make a description in a formal language, do it. It can safe the part of your body where you sit on.
Let me take the questions you asked as a description of the problems you saw and let me take PARI/GP as an example for no other reason other than that I use it often and am familiar with it.
PARI/GP is text-based and uses a terminal as the main medium. The modern terminals are quite fast. The language it uses it easy to learn, although hard to master. As it is with every language, I think 😉
The maximum allowed exponent is 2^32 as far as I know and of course you cannot have more limbs than the largest possible native integer allows, that means that the largest possible number on 64 bit systems is (2^64)^(2^64)-1 which is a number with roughly 355,599,885,758,256,416,694 decimal digits. I think that is enough. If it isn’t enough you can use these numbers as limbs for a new form of Bigint (that is: you use 2^64 bit long limbs instead of 64 bit long ones). But don’t forget that each such limb needs one petabyte of memory!
Yes.
Don’t know, didn’t try.
Why should I?
If you want a widespread access use the lowest common denominator. Adjust “widespread” and “lowest” to your needs, that is: if you use anything essential that cannot be done (or is just to much hassle) with another version than use that version, otherwise use a lower one.
At the very least make it clear in the requirements.
Didn’t met my sister yet but I have a long weekend to come and if I have to make an account at Google’s Playstore than *sigh* be it.
Do you do it yourself or do you have a sports student at hand? I don’t have much expertise in that but the female anatomy is, as far as I remember, a bit different so you need at least one genetically female one, too.
The pictures you used in the app look like stock-photos, are they?
Looked it up at Youtube, looks very…uhm…healthy 😉
WordPress uses HTML only now. You need a plugin to use bbcode which is not installed here.
Ah, just in the moment when I was going to press send you made a new comment 😉
I’ll take the liberty to add my answers here, ok?
O(n(log n)(loglog n))
The sieve works by eliminating every prime and its multiples and because the distribution of primes gets thinner when approaching infinity you’ll come up with the above complexity. A short explanation at stackoverflow.
You’ll find examples on the net but if you want my own opinion: it’s quite a lot of work, especially if you start from scratch.
Ah, thanks!
But…but…I payed for it! 😉
“plenty of time for people to update” is not a year. Make that ten years, sometimes even more, especially in businesses.
From long and painful experiences: do not assume anything, put it in the requirements.
For example: if you think that nobody uses DOS any more, especially not in business—be prepared for a lot of surprises.
I can easily install runtimes for Java 1, 2, 5, 6, and 7 in parallel but there is nothing prepared for Java 8 so I would have to do it myself. Its not very complicated but I have not much use for Java so I would like to avoid it.
It is also a legal problem, albeit a small one. I’m not that strict.
And I thought 128 MiB was quite generous! 😉
But serious: that is what I normally start with. The program must detect that and groan in one way or another if that amount of memory is not enough.
I saw some lines regarding memory checks in your code but I would need to either do a thorough analysis to be sure those hold or do it by just being a bit stingy with memory in the first place. The latter is not as complete as the former but it has a high probability to find the most sensible errors.
Oh just saw your reply, here’s a link to my post: http://chaitanyavarier.com/2015/08/13/pe-16/
I added another note in my first post detailing the minimum version of Java required.
Hello,
I’m not sure if you’ve been able to see your comments on my blog yet, but if not you can check them out, as I’ve posted replies.