Natsumi (2005-04-06) Synopsis gcc natsumi.c -o natsumi ./natsumi <integer> [...] For each command line argument, Natsumi will print out a representation of it using 120 and basic operators only. Douglas Adams fans may prefer this instead: mv natsumi.c deepthought.c gcc deepthought.c -o deepthought ./deepthought <integer> [...] ... and expressions will be in terms of 42 instead of 120. Details Natsumi will reason how everything starts with 120... well, all integers, at least. Inspired by Nekoneko Soft's "120en no natsu" (summer of 120 yen). Source code is meant to resemble Natsumi from the game. For those who don't know the story: Two characters met at a vending machine in the summer, discovered that they have the ability to get free products out of any vending machine by hitting it together... thus they toured around the neighborhood and had a great time, even if the vending machines never give them what they had in mind and never dispensed more than two products. They found this special ability to be no longer working at the end of the second day. Though by then, both realized what they wanted wasn't the this ability, but merely an excuse to be together. Awkward at first but regular couple at last... the 1:6 billion chance encounter that all started with 120 yen. Most vending machines should still operate at 120 yen per product... If anyone else has excess affection for a particular integer and wants to replace all numeric constants with The One, here is the program for you ^_^; Known issues - Specifying -2147483648 causes a crash. - Some file names causes output to take a long time to execute. - Not all outputs are optimal. - Source is ASCII dependent. Implementation Obviously any number can be represented as (120+120+...)/120, using exactly (n+1) 120s to represent n. Something like this: #include<stdio.h> void main(int n,char**a) { for(;*++a?sscanf(*a,"%d",&n):0;puts(")/120")) for(printf("%d = (120",n);--n;printf("+120")); } ... which wouldn't be terribly interesting. Natsumi does much better in trying to generate expressions with minimal number of 120s, using dynamic programming: 1. Start with a set of known optimal expressions. 2. Combine element pairs from the set using one of four basic operations. The results are also optimal if they are not in the optimal set already. 3. Add results to set, go to step 1 and repeat until the number in question is in the optimal set. In practice, because the size of integers are finite and the size of table is finite, some results at step 2 will have to be dropped, and remaining table entries will have to be filled using less optimal expressions. Then, because we are not guaranteed to get all the optimal expressions in every iteration, the entire table must be filled to get the best expression available for every cell entry. Natsumi should actually continue to run the steps a few more times on the full table, but few people have enough patience for that. Thus, not all output expressions are optimal... Maybe users can take it as a challenge to find expressions shorter than Natsumi's output ^_^; For example, Natsumi outputs 22 120s for 2073600000, but this can be computed using only 9 120s. Some heuristics might also apply to eliminating more parentheses... Because -(-2147483648) == -2147483648 in signed 32bit, specifying -2147483648 will cause Natsumi to crash. Numbers from -2147483647 to 2147483647 are okay though. About the output expressions: Natsumi guarantees no divisions where the denominator is zero or where the quotient is not an integer, but overflows are something else. Depending on the order of evaluation, the intermediate result may overflow 32bit signed int. So then: - Evaluating them all as doubles should work. - Evaluating them by hand eventually works. - Evaluating them with Perl definitely works, something like: perl -e 'while(<>){print eval;print"\n";}' About using the file name to select expression base: obviously I tweaked the numbers such that "natsumi.c" maps to 120 and "deepthought.c" maps to 42. I wanted to make the number configurable without adding an extra parameter, without changing the source, and without wasting any lines for preprocessor. So source file name it is. Because of the file name bit, the code becomes ASCII dependent. Also, it's not so easy to select a number this way, though not impossible. If user wanted 54, for example (because 42 is six times nine = 54), they would need some name in l33tspeak like "de3p7h0ugh7.c". Guessing the right name for the desired number is left as an exercise to the reader, I only promised 42 and 120. Well, and 54 too. The algorithm should work for any number greater than 3 (and therefore all file names), although some numbers take longer to generate the table than others, some probably *too* long. This can be mediated by specifying a smaller table size, by modifying the "z=46340" bit in line 6. 46340 is the highest value supported on 32bit machines and produces the best results, setting it to a lower value will make Natsumi run faster, at the cost of losing some optimal solutions.
RAR | ZIP | / | |
2022-03-13 |