File:MinMultTree.gif
Jump to navigation
Jump to search
Size of this preview: 800 × 486 pixels. Other resolutions: 320 × 195 pixels | 640 × 389 pixels | 1,024 × 623 pixels | 1,541 × 937 pixels.
Original file (1,541 × 937 pixels, file size: 32 KB, MIME type: image/gif)
Summary
| Description |
English: Minumum-effort multiplication tree, inspired by Knuth.1997, Sect.4.6.3, Fig.15, p.465.
Shows the minimum number of multiplications needed to obtain the nth power, for 1 ≤ n ≤ 100. Node colors are by depth, with the top 3 levels in black. An edge color indicates the level of the factor the parent node has to be multiplied with to obtain the child node. For example, the rightmost edge at the bottom ("65 --> 81") indicates that the 81st power can be obtained from the 65th power by multiplying it with the ancester node of level 5, viz. 16.
For each fixed n, the C source code scheme below can be used to compute the nth power of Donald Ervin Knuth (1997) Seminumerical Algorithms, The Art of Computer Programming, 2 (3rd ed.), Reading/MA: Addison-Wesley ISBN: 0-201-89684-2. |
| Date | |
| Source | Own work |
| Author | Jochen Burghardt |
C source code scheme
|
|---|
double minMult(
double a1)
{
double const a2 = a1 * a1 ;
double const a3 = a2 * a1 ;
double const a4 = a2 * a2 ;
double const a5 = a3 * a2 ;
double const a6 = a3 * a3 ;
double const a7 = a5 * a2 ;
double const a8 = a4 * a4 ;
double const a9 = a8 * a1 ;
double const a10 = a5 * a5 ;
double const a11 = a10 * a1 ;
double const a12 = a6 * a6 ;
double const a13 = a9 * a4 ;
double const a14 = a7 * a7 ;
double const a15 = a12 * a3 ;
double const a16 = a8 * a8 ;
double const a17 = a9 * a8 ;
double const a18 = a16 * a2 ;
double const a19 = a14 * a5 ;
double const a20 = a10 * a10;
double const a21 = a11 * a10;
double const a22 = a11 * a11;
double const a23 = a20 * a3 ;
double const a24 = a12 * a12;
double const a25 = a24 * a1 ;
double const a26 = a13 * a13;
double const a27 = a15 * a12;
double const a28 = a14 * a14;
double const a29 = a28 * a1 ;
double const a30 = a15 * a15;
double const a31 = a21 * a10;
double const a32 = a16 * a16;
double const a33 = a32 * a1 ;
double const a34 = a17 * a17;
double const a35 = a26 * a9 ;
double const a36 = a18 * a18;
double const a37 = a36 * a1 ;
double const a38 = a19 * a19;
double const a39 = a27 * a12;
double const a40 = a20 * a20;
double const a41 = a40 * a1 ;
double const a42 = a21 * a21;
double const a43 = a34 * a9 ;
double const a44 = a22 * a22;
double const a45 = a30 * a15;
double const a46 = a23 * a23;
double const a47 = a46 * a1 ;
double const a48 = a24 * a24;
double const a49 = a33 * a16;
double const a50 = a25 * a25;
double const a51 = a48 * a3 ;
double const a52 = a26 * a26;
double const a53 = a51 * a2 ;
double const a54 = a27 * a27;
double const a55 = a54 * a1 ;
double const a56 = a28 * a28;
double const a57 = a56 * a1 ;
double const a58 = a29 * a29;
double const a59 = a56 * a3 ;
double const a60 = a30 * a30;
double const a61 = a52 * a9 ;
double const a62 = a31 * a31;
double const a63 = a60 * a3 ;
double const a64 = a32 * a32;
double const a65 = a64 * a1 ;
double const a66 = a33 * a33;
double const a67 = a66 * a1 ;
double const a68 = a34 * a34;
double const a69 = a68 * a1 ;
double const a70 = a35 * a35;
double const a71 = a70 * a1 ;
double const a72 = a36 * a36;
double const a73 = a72 * a1 ;
double const a74 = a37 * a37;
double const a75 = a60 * a15;
double const a76 = a38 * a38;
double const a77 = a43 * a34;
double const a78 = a39 * a39;
double const a79 = a78 * a1 ;
double const a80 = a40 * a40;
double const a81 = a65 * a16;
double const a82 = a41 * a41;
double const a83 = a80 * a3 ;
double const a84 = a42 * a42;
double const a85 = a80 * a5 ;
double const a86 = a43 * a43;
double const a87 = a86 * a1 ;
double const a88 = a44 * a44;
double const a89 = a88 * a1 ;
double const a90 = a45 * a45;
double const a91 = a90 * a1 ;
double const a92 = a46 * a46;
double const a93 = a92 * a1 ;
double const a94 = a47 * a47;
double const a95 = a85 * a10;
double const a96 = a48 * a48;
double const a97 = a96 * a1 ;
double const a98 = a49 * a49;
double const a99 = a96 * a3 ;
double const a100 = a50 * a50;
}
|
Licensing
I, the copyright holder of this work, hereby publish it under the following license:
 
|
This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication. |
| The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
|
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 13:44, 22 August 2025 | | 1,541 × 937 (32 KB) | wikimediacommons>Jochen Burghardt | Uploaded own work with UploadWizard |
File usage
The following page uses this file:
