(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 24569, 896]*) (*NotebookOutlinePosition[ 25266, 920]*) (* CellTagsIndexPosition[ 25222, 916]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[{ "Generally efficient numerical programming in ", StyleBox["Mathematica", FontSlant->"Italic"], " " }], "Title"], Cell[TextData[{ StyleBox["Mathematica", FontSlant->"Italic"], " allows you to write simple programs which can work for a very general \ class of inputs. For numerical programs, a few simple principles allows you \ to write programs which are efficient for both machine numbers and bignums. \ In this talk, I will briefly describe the types of numbers ", StyleBox["Mathematica", FontSlant->"Italic"], " works with, then go on to show you two examples which demonstrate what I \ consider to be the essential principles of efficient numerical programming in \ ", StyleBox["Mathematica", FontSlant->"Italic"], "." }], "Text"], Cell["\<\ You should be able to find the notebook and packages for this talk at \ http://members.wri.com/rknapp/DeveloperConference99\ \>", "Text"], Cell[CellGroupData[{ Cell[TextData[{ "Numbers in ", StyleBox["Mathematica", FontSlant->"Italic"], " " }], "Section"], Cell[TextData[{ "One of the important features of ", StyleBox["Mathematica", FontSlant->"Italic"], " is that it works with a variety of types of numbers, using a consistent \ set of semantics to combine different types when necessary." }], "Text"], Cell[CellGroupData[{ Cell["Exact Quantities", "Subsection"], Cell[BoxData[ \(Pi\ < \ E\)], "Input", CellLabel->"In[1]:="], Cell[BoxData[ \(\(100!\)\)], "Input", CellLabel->"In[2]:="], Cell[BoxData[ \(NumericQ[Sin[E]]\)], "Input", CellLabel->"In[3]:="], Cell[BoxData[ \(Precision[Sin[E]]\)], "Input", CellLabel->"In[18]:="], Cell["\<\ Semantic note: Combinations of exact expression with exact expressions generally comes out exact. When combining with inexact expressions, the final precision is typically determined by the precisions of the inexact parts. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Machine real numbers", "Subsection"], Cell[TextData[{ "In ", StyleBox["Mathematica", FontSlant->"Italic"], ", when you use machine numbers, you typically get whatever your machine's \ hardware and library functions give you. For example:" }], "Text"], Cell[BoxData[ \(Sin[2. ]\)], "Input", CellLabel->"In[4]:="], Cell[TextData[{ "Computations with machine numbers can be done very quickly. In ", StyleBox["Mathematica", FontSlant->"Italic"], " 4, PackedArrays give even better speed. For example:" }], "Text"], Cell[BoxData[{ \(\(data\ = \ Table[Random[], {1000000}];\)\), "\[IndentingNewLine]", \(Timing[\(Sin[data];\)]\)}], "Input", CellLabel->"In[5]:="], Cell["\<\ Semantic note: Even though machine numbers technically have precision equal to $MachinePrecision, this precision is not guaranteed in any way. Thus combinations of machine numbers with other types of numbers attempts coercion \ to machine numbers. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Bignums", "Subsection"], Cell["\<\ These are approximate real numbers too large to fit into machine hardware real numbers (on most machines this is IEEE double precision with a 53 bit (approx 16 digit mantissa) and an 8 bit exponent.) \ \>", "Text"], Cell["This has too large an exponent, so it is given by a bignum:", "Text"], Cell[BoxData[ \(E^1000. \)], "Input", CellLabel->"In[155]:="], Cell["\<\ The arithmetic for bignums is implemented in software. Because of this, it is possible to keep track of the number of significant bits through significance arithmetic. If you are interested in details on this, I suggest \ looking at some excellent notebooks written by Mark Sofroniou on the subject. \ \>", "Text"], Cell["\<\ Here is an example where keeping track of precision makes a big difference: \ \>", "Text"], Cell[BoxData[ \(arg\ = \ 2^60\ - \ 21\)], "Input", CellLabel->"In[11]:="], Cell["\<\ Even though the argument is large, the machine library sine funciton returns a value: \ \>", "Text"], Cell[BoxData[ \(Sin[N[arg]]\)], "Input", CellLabel->"In[12]:="], Cell["\<\ However, this is identical to the value for sine of 2^60, which is clearly wrong. \ \>", "Text"], Cell[BoxData[ \(%\ === \ Sin[2. ^60]\)], "Input", CellLabel->"In[13]:="], Cell["\<\ If we use precision > $MachinePrecision, then the computation keeps track of precision: \ \>", "Text"], Cell[BoxData[ \(Sin[N[arg, 17]]\)], "Input", CellLabel->"In[14]:="], Cell["The zero means we have no precision in the result! ", "Text"], Cell[BoxData[ \(Precision[%]\)], "Input", CellLabel->"In[15]:="], Cell["\<\ For precisions > $MachinePrecision, the command N is adaptive, so \ \>", "Text"], Cell[BoxData[ \(N[Sin[arg], 17]\)], "Input", CellLabel->"In[168]:="], Cell["\<\ internally uses higher precision to get a result which is good to 17 digits. \ \>", "Text"], Cell["\<\ The disadvantage of using bignums is that software arithmetic is bound to be slower than hardware arithmetic. \ \>", "Text"], Cell[BoxData[{ \(\(data\ = \ SetPrecision[Take[data, 1000], 17];\)\), "\[IndentingNewLine]", \(Timing[\(Sin[data];\)]\)}], "Input", CellLabel->"In[16]:="], Cell[TextData[{ "In ", StyleBox["Mathematica", FontSlant->"Italic"], " 4, a lot of effort was put into making sure that with very high \ precision, operations are as efficient as possible." }], "Text"], Cell[TextData[{ "In my opinion, the improvements in ", StyleBox["Mathematica", FontSlant->"Italic"], " 4 are shown off well by the following question which I was asked by a \ representative of the Japanese ", StyleBox["Mathematica", FontSlant->"Italic"], " users group in late 1995:" }], "Text"], Cell[TextData[{ "\"Can ", StyleBox["Mathematica", FontSlant->"Italic"], " compute Pi to 5,000,000 digits in principle? In practice?\"" }], "Text"], Cell["\<\ At the time the question was asked, the answer was basically: in prinicple, yes, but in practice, it could take days or weeks. Though I would like to do \ it before your very eyes, it still takes a little long. Nonetheless, the computation is practical to do in the time of a coffee break: \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\($MaxPrecision\ = \ Infinity;\)\), "\[IndentingNewLine]", \(Timing[\(pi50k\ = \ N[Pi, 5000000];\)]\)}], "Input", Evaluatable->False], Cell[BoxData[ \({1106.48`\ Second, Null}\)], "Output"] }, Closed]], Cell[TextData[{ "Yes, part of the speed improvement has to do with the nice 333MhZ \ processor I have on this machine, but that is actually a small part of the \ story. ", StyleBox["Mathematica", FontSlant->"Italic"], " 3.0 would take days to weeks on the same computation on this machine." }], "Text"], Cell["\<\ The reason I consider this a good example is that there are two distinct improvements which went into this functionality. \ \>", "Text"], Cell[TextData[{ "First, multiplication is done with asymptotically efficient algorithms. \ This change effects any computation you do in ", StyleBox["Mathematica", FontSlant->"Italic"], " with more than a few hundred digits. You will see an example of how this \ algorithm works in a few minutes." }], "Text"], Cell[TextData[{ "Second, the algorithm for computing \[Pi] was improved to take advantage \ of the faster multiplication. This has been done for many fundamental \ functions in ", StyleBox["Mathematica", FontSlant->"Italic"], ", such as factorials, exponentials, trig functions, and the like." }], "Text"], Cell[TextData[{ "The end result is that, using the same syntax and commands as in ", StyleBox["Mathematica", FontSlant->"Italic"], " 3.0, you may get results an order of magnitude faster with ", StyleBox["Mathematica", FontSlant->"Italic"], " 4. " }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Some programming principles", "Section"], Cell["\<\ These are general principles. They apply to all types of numbers, including those stored in packed arrays, where using these principles can make an even bigger difference.\ \>", "Text"], Cell[CellGroupData[{ Cell["Try to avoid using individual parts of lists", "Subsubsection"], Cell[TextData[{ "To help see the differences, I will use an alternative way of computing \ the ", ButtonBox["time", ButtonData:>{"time.nb", None}, ButtonStyle->"Hyperlink"], " it takes an expression to evaluate" }], "Text"], Cell[BoxData[ \(time[\(Table[Sin[data[\([i]\)]], {i, Length[data]}];\)]\)], "Input", CellLabel->"In[19]:="], Cell[BoxData[ \(\(data\ = \ N[data];\)\)], "Input", CellLabel->"In[20]:="], Cell[BoxData[ \(time[\(Table[Sin[data[\([i]\)]], {i, Length[data]}];\)]\)], "Input", CellLabel->"In[21]:="], Cell[BoxData[ \(time[\(Sin[data];\)]\)], "Input", CellLabel->"In[22]:="], Cell[BoxData[{ \(\(f[x_]\ := \ Sin[x];\)\), "\[IndentingNewLine]", \(time[Table[f[data[\([i]\)]], {i, Length[data]}]]\)}], "Input", CellLabel->"In[23]:="], Cell[BoxData[ \(time[f[data]]\)], "Input", CellLabel->"In[27]:="] }, Closed]], Cell[CellGroupData[{ Cell["\<\ Use functional operations which operate on large chunks of your data.\ \>", "Subsubsection"], Cell["\<\ This is really the same as the one above, but it is so important, I give it twice!\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Try to avoid copying", "Subsubsection"], Cell["\<\ Just the other day I got a question through tech. support about how to replace submatrices efficiently. They had been using ReplacePart. Here is an example: \ \>", "Text"], Cell[BoxData[ \(\(matrix\ = \ Table[Random[], {100}, {100}];\)\)], "Input", CellLabel->"In[25]:="], Cell[BoxData[ \(parts\ = \ Transpose[{Range[10, 90], 50\ + \ 0\ Range[10, 90]}]\)], "Input", CellLabel->"In[26]:="], Cell[BoxData[ \(time[matrix\ = \ ReplacePart[matrix, 0. , \ parts]]\)], "Input", CellLabel->"In[27]:="], Cell[BoxData[ \(Extract[matrix, \ parts]\)], "Input", CellLabel->"In[28]:="], Cell[BoxData[ \(time[Extract[matrix, \ parts]]\)], "Input", CellLabel->"In[29]:="], Cell["Here is a faster way:", "Text"], Cell[BoxData[ \(time[matrix[\([Range[10, 90], \ 50]\)]\ = \ 0. ]\)], "Input", CellLabel->"In[30]:="], Cell["Part is typically faster than Extract for submatrices", "Text"], Cell[BoxData[ \(time[matrix[\([Range[10, 90], 50]\)]]\)], "Input", CellLabel->"In[35]:="] }, Closed]], Cell[CellGroupData[{ Cell["Don't use Append in a loop", "Subsubsection"], Cell["..or Prepend or AppendTo or PrependTo or Join.", "Text"], Cell["\<\ This is actually the previous principle repeated in a specific instance.\ \>", "Text"], Cell["\<\ This example is a bit contrived, but it actually closely relates to solve differential equations with automatic time step control. (Subtle advertisment for my next talk later today.)\ \>", "Text"], Cell[BoxData[ \(\(randomlist[x_]\ := \ Module[{a\ = \ {}, \ sum\ = \ 0}, \[IndentingNewLine]While[ sum\ < \ x, \[IndentingNewLine]r\ = \ Random[]; \[IndentingNewLine]AppendTo[a, \ r]; \[IndentingNewLine]sum\ += \ r]; \[IndentingNewLine]a];\)\)], "Input", CellLabel->"In[1]:="], Cell[BoxData[ \(randomlist[5]\)], "Input", CellLabel->"In[27]:="], Cell["\<\ That seemed pretty fast, but when we compute over a wider range of values. Here I use the precomputed data to save time\ \>", "Text"], Cell[BoxData[ \(\(timetable\ = \ \((Hold[ Table[\[IndentingNewLine]SeedRandom[ 1234]; \[IndentingNewLine]{n\ = \ 2^k, \ time[randomlist[n]]}, \[IndentingNewLine]{k, 12}]]; {{2, 0.00044921875000000083`}, {4, 0.000722656249999995`}, {8, 0.0012500000000000011`}, {16, 0.0023437500000000056`}, {32, 0.004687500000000011`}, {64, 0.009531250000000102`}, {128, 0.020312499999999956`}, {256, 0.047812500000000036`}, {512, 0.13374999999999915`}, {1024, 0.427500000000002`}, {2048, 1.5900000000000034`}, {4096, 5.859999999999999`}})\);\)\)], "Input", CellLabel->"In[32]:="], Cell["... it eventually slows down a lot", "Text"], Cell[BoxData[ \(\(ListPlot[timetable, \ PlotJoined \[Rule] True, \ PlotRange \[Rule] All];\)\)], "Input", CellLabel->"In[33]:="], Cell[BoxData[ \(Fit[timetable, \ {1, x, x^2}, x]\)], "Input", CellLabel->"In[10]:="], Cell["Here is a better way to do it.", "Text"], Cell[BoxData[ \(\(betterrandomlist[x_]\ := \ Module[{sum\ = \ 0}, \[IndentingNewLine]NestWhileList[Random[] &, \ Random[], \ \((\((sum\ += \ #)\)\ < \ x)\) &]];\)\)], "Input", CellLabel->"In[6]:="], Cell[BoxData[ \(betterrandomlist[5]\)], "Input", CellLabel->"In[7]:="], Cell["\<\ Now check timings for this command (again precomputed so you don't ahve to \ wait)\ \>", "Text"], Cell[BoxData[ \(\(timetable2\ = \ \((Hold[ Table[\[IndentingNewLine]SeedRandom[ 1234]; \[IndentingNewLine]{n\ = \ 2^k, \ time[betterrandomlist[n]]}, \[IndentingNewLine]{k, 12}]]; {{2, 0.0004736328125000029`}, {4, 0.0008007812500000003`}, {8, 0.0014453125000000039`}, {16, 0.0028124999999999956`}, {32, 0.005351562500000018`}, {64, 0.011250000000000093`}, {128, 0.021093750000000355`}, {256, 0.04187500000000011`}, {512, 0.08375000000000021`}, {1024, 0.16750000000000043`}, {2048, 0.332499999999996`}, {4096, 0.6749999999999972`}})\);\)\)], "Input", CellLabel->"In[8]:="], Cell[BoxData[ \(\(ListPlot[timetable2, \ PlotJoined \[Rule] True, \ PlotRange \[Rule] All];\)\)], "Input", CellLabel->"In[9]:="], Cell[BoxData[ \(Fit[timetable2, \ {1, x, x^2}, x]\)], "Input", CellLabel->"In[11]:="], Cell["Compare the size of the quadratic coefficient.", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["\<\ Think carefully about how many things will have to be evaluated.\ \>", "Subsubsection"], Cell["\<\ This is subtle, but important. Here is an example which illustrates the idea \ \>", "Text"], Cell[BoxData[ \(\(n\ = \ 10000;\)\)], "Input", CellLabel->"In[12]:="], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[ For[sum\ = \ 0; i\ = \ 1, \ i\ \[LessEqual] \ n, \ \(i++\), \ sum\ += \ i]; \ sum]\)], "Input", CellLabel->"In[13]:="], Cell[BoxData[ \({0.37`\ Second, 50005000}\)], "Output", CellLabel->"Out[13]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[sum\ = \ 0; \ Do[sum\ += \ i, {i, n}]; \ sum]\)], "Input", CellLabel->"In[14]:="], Cell[BoxData[ \({0.17000000000000004`\ Second, 50005000}\)], "Output", CellLabel->"Out[14]="] }, Open ]], Cell["The example below is a nice trick for packed arrays...", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(time[Apply[Plus, \ Range[n]]]\)], "Input", CellLabel->"In[15]:="], Cell[BoxData[ \(0.017656250000000002`\)], "Output", CellLabel->"Out[15]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(time[Tr[Range[n]]]\)], "Input", CellLabel->"In[16]:="], Cell[BoxData[ \(0.00028320312500000003`\)], "Output", CellLabel->"Out[16]="] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["\<\ When you can't possibly avoid doing one of the first two, try to use the compiler.\ \>", "Subsubsection"], Cell["\<\ Here is a cute example which shows how asymptotically faster multiplication works at the same time. \ \>", "Text"], Cell[BoxData[{ \(\(a\ = \ 1839081381093812098309830918381238183908381038138;\)\), "\n", \(\ \[IndentingNewLine]\), "\n", \(\(b\ = \ 8237489274892747624237592768267459874897489724987284972897489274728497\ 289478927489274982734987238497;\)\)}], "Input", CellLabel->"In[17]:="], Cell["\<\ To simplify the discussion, I will use radix 10, though the code written below will work for any positive integer radix. \ \>", "Text"], Cell[BoxData[ \(\(r\ = 10;\)\)], "Input", CellLabel->"In[20]:="], Cell[BoxData[{ \(\(A\ = \ Reverse[IntegerDigits[a, r]];\)\), "\[IndentingNewLine]", \(\(B\ = \ Reverse[IntegerDigits[b, r]];\)\)}], "Input", CellLabel->"In[21]:="], Cell[BoxData[ \(len\ = \ 2*Max[Length[A], \ Length[B]]\)], "Input", CellLabel->"In[23]:="], Cell["\<\ Here is a way to multiply the two numbers by using the discrete convolution theorem on the list of digits. \ \>", "Text"], Cell[BoxData[ \(AB\ = \ Round[Take[ InverseFourier[ Fourier[PadRight[A, len]] Fourier[PadRight[B, len]], \ FourierParameters \[Rule] {\(-1\), 1}], Length[A]\ + \ Length[B]]]\)], "Input", CellLabel->"In[24]:="], Cell["\<\ ...but there is a problem in that you need to deal with the carries. \ \>", "Text"], Cell[BoxData[ \(PropagateCarries[x_, \ \ r_]\ := \ Module[{car\ = \ 0, \ res\ = \ x, \ t}, \[IndentingNewLine]Do[\[IndentingNewLine]t\ = \ res[\([i]\)]\ + \ car; \[IndentingNewLine]car\ = \ Quotient[t, \ r]; \[IndentingNewLine]res[\([i]\)]\ \ = \ t\ - \ r*car, \[IndentingNewLine]{i, Length[x]}]; \[IndentingNewLine]If[Last[res]\ \[Equal] \ 0, \ Drop[res, \ \(-1\)], res]]\)], "Input", CellLabel->"In[25]:="], Cell[BoxData[ \(PropagateCarries[AB, \ r]\)], "Input", CellLabel->"In[27]:="], Cell["Now check the result...", "Text"], Cell[BoxData[ \(FromDigits[Reverse[%], 10]\ - \ a*b\)], "Input", CellLabel->"In[28]:="], Cell[TextData[{ StyleBox["Mathematica", FontSlant->"Italic"], " 4 provides a more convenient (and generally faster way) to do this via \ the discrete convolution command ListConvolve" }], "Text"], Cell[BoxData[ \(ListConvolve[A, \ B, \ {1, Length[A] + 1}, \ 0]\)], "Input", CellLabel->"In[29]:="], Cell["using this, make a function to do the job", "Text"], Cell[BoxData[ \(\(ListMultiply[r_]\)[x_, \ y_]\ := \ \[IndentingNewLine]\ PropagateCarries[ListConvolve[x, \ y, \ {1, Length[x]\ + \ 1}, \ 0], \ r]\)], "Input", CellLabel->"In[30]:="], Cell[BoxData[ \(\(ListMultiply[r]\)[A, B]\)], "Input", CellLabel->"In[31]:="], Cell["or with another radix:", "Text"], Cell[BoxData[ \(\(ListMultiply[27]\)[Reverse[IntegerDigits[a, 27]], Reverse[IntegerDigits[b, 27]]]\)], "Input", CellLabel->"In[36]:="], Cell[BoxData[ \(BaseForm[a*b, 27]\)], "Input", CellLabel->"In[37]:="], Cell[BoxData[ \(a*b\ - \ FromDigits[Reverse[%%], \ 27]\)], "Input", CellLabel->"In[38]:="], Cell["Now lets try this with a bigger number", "Text"], Cell[BoxData[{ \(\(a\ = \ Random[Integer, \ {10^99999, \ 10^100000}];\)\), "\[IndentingNewLine]", \(\(b\ = \ \ Random[ Integer, \ {10^99999, \ 10^100000}];\)\), "\[IndentingNewLine]", \(Timing[A\ = \ Reverse[IntegerDigits[a, r]]; B\ = \ Reverse[IntegerDigits[b, r]];]\)}], "Input", CellLabel->"In[39]:="], Cell[BoxData[ \(Timing[\(\(ListMultiply[r]\)[A, B];\)]\)], "Input", CellLabel->"In[42]:="], Cell[BoxData[ \(Timing[\(AB\ = \ ListConvolve[A, B, {1, Length[A]\ + \ 1}, 0];\)]\)], "Input", CellLabel->"In[43]:="], Cell["Here is an alternate way to do the carries:", "Text"], Cell[BoxData[ \(ListPropagateCarries[x_, \ r_]\ := \ \[IndentingNewLine]Module[{car}, \ \[IndentingNewLine]FixedPoint[ Function[ car\ = \ Quotient[#, r]; \ \[IndentingNewLine]#\ - \ r*car\ + \ RotateRight[car]], \ x, \ 10]]\)], "Input", CellLabel->"In[44]:="], Cell[BoxData[ \(Timing[\(ListPropagateCarries[AB, \ r];\)]\)], "Input", CellLabel->"In[45]:="], Cell[TextData[{ "If we can bear to restrict ourselves to reaonably small radix, then we can \ use the ", StyleBox["Mathematica", FontSlant->"Italic"], " compiler." }], "Text"], Cell[BoxData[ \(\(CompiledPropagateCarries\ = \ Compile[{{x, \ _Integer, \ 1}, \ {r, \ _Integer}}, Module[{car\ = \ 0, \ res\ = \ x, \ t\ = \ 0}, \[IndentingNewLine]Do[\[IndentingNewLine]t\ = \ res[\([i]\)]\ + \ car; \[IndentingNewLine]car\ = \ Quotient[t, \ r]; \[IndentingNewLine]res[\([i]\)]\ \ = \ t\ - \ r*car, \[IndentingNewLine]{i, Length[x]}]; \[IndentingNewLine]If[ Last[res]\ \[Equal] \ 0, \ Drop[res, \ \(-1\)], res]]];\)\)], "Input", CellLabel->"In[46]:="], Cell[BoxData[ \(Timing[\(CompiledPropagateCarries[AB, \ r];\)]\)], "Input", CellLabel->"In[47]:="], Cell[BoxData[{ \(\(Clear[PropagateCarries];\)\), "\[IndentingNewLine]", \(\(PropagateCarries\ = \ CompiledPropagateCarries;\)\)}], "Input", CellLabel->"In[48]:="], Cell[TextData[{ "Even with this work, it is still slower than the internal ", StyleBox["Mathematica", FontSlant->"Italic"], " Times:" }], "Text"], Cell[BoxData[ \(Timing[\(\(ListMultiply[r]\)[A, B];\)]\)], "Input", CellLabel->"In[50]:="], Cell[BoxData[ \(Timing[\(a*b;\)]\)], "Input", CellLabel->"In[51]:="], Cell[TextData[{ "which is using basically the same algorithm. If we turn it off, you get \ the ", StyleBox["Mathematica", FontSlant->"Italic"], " 3.0 speed." }], "Text"], Cell[BoxData[ \(\(Developer`SetSystemOptions["\" \[Rule] Infinity];\)\)], "Input", CellLabel->"In[52]:="], Cell[BoxData[ \(Timing[\(a*b;\)]\)], "Input", CellLabel->"In[53]:="] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["More involved Examples", "Section"], Cell[TextData[{ "There are many examples I could show you. I have picked two particular \ ones.\n\nThe first example came from a user I helped to speed up his program \ to compute solutions of the Schrodinger equation using the ", ButtonBox["Crank-Nicholson", ButtonData:>{"Crank-Nicholson2.nb", None}, ButtonStyle->"Hyperlink"], " method. ", ButtonBox["Analysis", ButtonData:>{"CrankNicholsonAnalysis.nb", None}, ButtonStyle->"Hyperlink"], " of the program led to a huge speed increase." }], "Text"], Cell[TextData[{ "The second example is from the demonstrative package \ LinearAlgebra`GaussianElimination. With some significant ", ButtonBox["modifications", ButtonData:>{"LUFactor.nb", None}, ButtonStyle->"Hyperlink"], ", the core routine of this package can be made nearly as fast as the built \ in code for bignums." }], "Text"] }, Closed]] }, Open ]] }, FrontEndVersion->"4.0 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 695}}, WindowSize->{496, 599}, WindowMargins->{{Automatic, 235}, {77, Automatic}}, StyleDefinitions -> "ArticleClassic.nb" ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1739, 51, 137, 5, 152, "Title"], Cell[1879, 58, 652, 15, 112, "Text"], Cell[2534, 75, 147, 3, 44, "Text"], Cell[CellGroupData[{ Cell[2706, 82, 105, 5, 57, "Section"], Cell[2814, 89, 258, 6, 61, "Text"], Cell[CellGroupData[{ Cell[3097, 99, 38, 0, 43, "Subsection"], Cell[3138, 101, 67, 2, 31, "Input"], Cell[3208, 105, 65, 2, 31, "Input"], Cell[3276, 109, 73, 2, 31, "Input"], Cell[3352, 113, 75, 2, 31, "Input"], Cell[3430, 117, 253, 7, 112, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[3720, 129, 42, 0, 27, "Subsection"], Cell[3765, 131, 224, 6, 70, "Text"], Cell[3992, 139, 65, 2, 70, "Input"], Cell[4060, 143, 208, 5, 70, "Text"], Cell[4271, 150, 157, 3, 70, "Input"], Cell[4431, 155, 277, 8, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4745, 168, 29, 0, 27, "Subsection"], Cell[4777, 170, 227, 6, 70, "Text"], Cell[5007, 178, 75, 0, 70, "Text"], Cell[5085, 180, 67, 2, 70, "Input"], Cell[5155, 184, 331, 9, 70, "Text"], Cell[5489, 195, 101, 4, 70, "Text"], Cell[5593, 201, 81, 2, 70, "Input"], Cell[5677, 205, 112, 5, 70, "Text"], Cell[5792, 212, 69, 2, 70, "Input"], Cell[5864, 216, 108, 5, 70, "Text"], Cell[5975, 223, 79, 2, 70, "Input"], Cell[6057, 227, 114, 5, 70, "Text"], Cell[6174, 234, 73, 2, 70, "Input"], Cell[6250, 238, 68, 0, 70, "Text"], Cell[6321, 240, 70, 2, 70, "Input"], Cell[6394, 244, 91, 4, 70, "Text"], Cell[6488, 250, 74, 2, 70, "Input"], Cell[6565, 254, 103, 5, 70, "Text"], Cell[6671, 261, 138, 5, 70, "Text"], Cell[6812, 268, 175, 4, 70, "Input"], Cell[6990, 274, 212, 6, 70, "Text"], Cell[7205, 282, 314, 9, 70, "Text"], Cell[7522, 293, 157, 5, 70, "Text"], Cell[7682, 300, 320, 8, 70, "Text"], Cell[CellGroupData[{ Cell[8027, 312, 163, 3, 70, "Input", Evaluatable->False], Cell[8193, 317, 58, 1, 70, "Output"] }, Closed]], Cell[8266, 321, 315, 7, 70, "Text"], Cell[8584, 330, 150, 5, 70, "Text"], Cell[8737, 337, 322, 7, 70, "Text"], Cell[9062, 346, 318, 7, 70, "Text"], Cell[9383, 355, 278, 8, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[9710, 369, 46, 0, 30, "Section"], Cell[9759, 371, 198, 4, 61, "Text"], Cell[CellGroupData[{ Cell[9982, 379, 69, 0, 33, "Subsubsection"], Cell[10054, 381, 238, 7, 70, "Text"], Cell[10295, 390, 113, 2, 70, "Input"], Cell[10411, 394, 81, 2, 70, "Input"], Cell[10495, 398, 113, 2, 70, "Input"], Cell[10611, 402, 78, 2, 70, "Input"], Cell[10692, 406, 166, 3, 70, "Input"], Cell[10861, 411, 71, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10969, 418, 102, 2, 25, "Subsubsection"], Cell[11074, 422, 107, 3, 44, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[11218, 430, 45, 0, 25, "Subsubsection"], Cell[11266, 432, 186, 6, 70, "Text"], Cell[11455, 440, 105, 2, 70, "Input"], Cell[11563, 444, 130, 3, 70, "Input"], Cell[11696, 449, 110, 2, 70, "Input"], Cell[11809, 453, 82, 2, 70, "Input"], Cell[11894, 457, 88, 2, 70, "Input"], Cell[11985, 461, 37, 0, 70, "Text"], Cell[12025, 463, 107, 2, 70, "Input"], Cell[12135, 467, 69, 0, 70, "Text"], Cell[12207, 469, 95, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[12339, 476, 51, 0, 25, "Subsubsection"], Cell[12393, 478, 62, 0, 27, "Text"], Cell[12458, 480, 96, 2, 27, "Text"], Cell[12557, 484, 209, 4, 61, "Text"], Cell[12769, 490, 354, 7, 151, "Input"], Cell[13126, 499, 71, 2, 31, "Input"], Cell[13200, 503, 145, 3, 44, "Text"], Cell[13348, 508, 721, 12, 311, "Input"], Cell[14072, 522, 50, 0, 27, "Text"], Cell[14125, 524, 143, 3, 51, "Input"], Cell[14271, 529, 90, 2, 31, "Input"], Cell[14364, 533, 46, 0, 27, "Text"], Cell[14413, 535, 229, 4, 71, "Input"], Cell[14645, 541, 76, 2, 31, "Input"], Cell[14724, 545, 106, 3, 27, "Text"], Cell[14833, 550, 730, 12, 311, "Input"], Cell[15566, 564, 143, 3, 51, "Input"], Cell[15712, 569, 91, 2, 31, "Input"], Cell[15806, 573, 62, 0, 27, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[15905, 578, 97, 2, 25, "Subsubsection"], Cell[16005, 582, 104, 5, 78, "Text"], Cell[16112, 589, 76, 2, 31, "Input"], Cell[CellGroupData[{ Cell[16213, 595, 167, 4, 51, "Input"], Cell[16383, 601, 84, 2, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[16504, 608, 112, 2, 31, "Input"], Cell[16619, 612, 99, 2, 30, "Output"] }, Open ]], Cell[16733, 617, 70, 0, 27, "Text"], Cell[CellGroupData[{ Cell[16828, 621, 87, 2, 31, "Input"], Cell[16918, 625, 80, 2, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[17035, 632, 76, 2, 31, "Input"], Cell[17114, 636, 82, 2, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[17245, 644, 116, 3, 42, "Subsubsection"], Cell[17364, 649, 126, 5, 78, "Text"], Cell[17493, 656, 312, 7, 171, "Input"], Cell[17808, 665, 147, 5, 78, "Text"], Cell[17958, 672, 71, 2, 31, "Input"], Cell[18032, 676, 176, 3, 51, "Input"], Cell[18211, 681, 97, 2, 31, "Input"], Cell[18311, 685, 133, 5, 70, "Text"], Cell[18447, 692, 270, 7, 70, "Input"], Cell[18720, 701, 94, 4, 70, "Text"], Cell[18817, 707, 504, 9, 70, "Input"], Cell[19324, 718, 83, 2, 70, "Input"], Cell[19410, 722, 39, 0, 70, "Text"], Cell[19452, 724, 94, 2, 70, "Input"], Cell[19549, 728, 204, 5, 70, "Text"], Cell[19756, 735, 105, 2, 70, "Input"], Cell[19864, 739, 57, 0, 70, "Text"], Cell[19924, 741, 207, 4, 70, "Input"], Cell[20134, 747, 83, 2, 70, "Input"], Cell[20220, 751, 38, 0, 70, "Text"], Cell[20261, 753, 147, 3, 70, "Input"], Cell[20411, 758, 75, 2, 70, "Input"], Cell[20489, 762, 97, 2, 70, "Input"], Cell[20589, 766, 54, 0, 70, "Text"], Cell[20646, 768, 363, 8, 70, "Input"], Cell[21012, 778, 96, 2, 70, "Input"], Cell[21111, 782, 136, 3, 70, "Input"], Cell[21250, 787, 59, 0, 70, "Text"], Cell[21312, 789, 315, 7, 91, "Input"], Cell[21630, 798, 100, 2, 31, "Input"], Cell[21733, 802, 187, 6, 44, "Text"], Cell[21923, 810, 616, 11, 191, "Input"], Cell[22542, 823, 104, 2, 31, "Input"], Cell[22649, 827, 174, 3, 51, "Input"], Cell[22826, 832, 155, 5, 27, "Text"], Cell[22984, 839, 96, 2, 31, "Input"], Cell[23083, 843, 74, 2, 31, "Input"], Cell[23160, 847, 181, 6, 44, "Text"], Cell[23344, 855, 145, 3, 51, "Input"], Cell[23492, 860, 74, 2, 31, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[23615, 868, 41, 0, 30, "Section"], Cell[23659, 870, 530, 12, 95, "Text"], Cell[24192, 884, 349, 8, 61, "Text"] }, Closed]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)