Natsumi (2005-04-06)


      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.


   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

   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.


   Obviously any number can be represented as (120+120+...)/120,
   using exactly (n+1) 120s to represent n.  Something like this:

      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.