How can I generate a best fit quadratic function?

Question

This is my first time using mathematica so I'm pretty confused. This question is based on the Sierpinski Triangle.

The figure below shows the percentage of total even entries and total odd entries through columns 10,20,30...1000

To generate that figure of the sideways parabola, I have this code:

ListPlot[
 {
  Table[
   {
    col,
    100. Total[
       Flatten[
        Table[
         If[
          EvenQ[Binomial[n, k]],
          1,
          0
          ],
         {n, 0, col, 1},
         {k, 0, n, 1}
         ],
        1
        ]
       ]/((col + 1) (col + 2)/2)
    },
   {col, 10, 1000, 5}
   ],
  Table[
   {
    col,
    100. Total[
       Flatten[
        Table[
         If[
          OddQ[Binomial[n, k]],
          1,
          0
          ],
         {n, 0, col, 1},
         {k, 0, n, 1}
         ],
        1
        ]
       ]/((col + 1) (col + 2)/2)
    },
   {col, 10, 1000, 5}
   ]
  },
 Filling -> Axis,
 PlotStyle -> {Blue, Orange},
 ImageSize -> Automatic
 ]

How can I generate the figure that shows the time it took to compute the even percentages through columns 10,...,500 and also show the parabola that best fits teh time data?

Also once I have that best-fit quadratic, how can I predict the time it would take to generate 1000 column?

Answer 1

Essentially, all that you have to do is take the code you use to generate the percentages, and put Timing[] around it like this:

timingdata = Table[
   {
    col,
    Timing[
    100. Total[
       Flatten[
        Table[
         If[
          EvenQ[Binomial[n, k]],
          1,
          0
          ],
         {n, 0, col, 1},
         {k, 0, n, 1}
         ],
        1
        ]
       ]/((col + 1) (col + 2)/2);
    ][[1]]
    },
   {col, 10, 500, 10}
   ]

Note that the changes I've made are:

• I'm assigning the result to the variable timingdata.
• I wrapped the entire piece of code that generates the percentage in Timing[].
• I suppressed the output of the percentage itself with a semicolon (this isn't really necessary but I typically prevent Mathematica from printing anything I don't need).
• I'm selecting only the first part of whatever Timing[] puts out by using [[1]]. I do this because Timing[] will output {the time, the result} but we don't need the result.
• I changed the iteration of col to be from 10 to 500 in steps of 10 like the graph.

From there, the fitting is actually pretty straight forward in Mathematica. If you look in the documentation, there are several tutorials for basic fits as well as more complicated ones.

For a simple function like this, I would recommend LinearModelFit. This function will actually return a FittedModel which is a model of the data with the best fit parameters already in there. What this means, is that you can easily ask for the value of the model for any input.

lm = LinearModelFit[timingdata, {t^2, t}, t];
lm[1000] (* ~ 1 second on my machine *)

Note that you don't have to use t as your variable, any variable name will do. The 1 second result makes sense if this is quadratic. If we double the input, we should expect an output that is 4 times larger. I get about 0.25 s for 500 columns, if we double the output to 1000 columns then we should expect around 1 second.

Something I struggled with when I was new to Mathematica was how to plot a function and a list of data at the same time, but it turns out it's not too hard:

Show[
  ListPlot[
     timingdata,
     PlotStyle -> Red],
  Plot[
     lm[t],
     {t, 0, 500},
     PlotRange -> Full]
]

I include PlotRange -> Full in my call to Plot[] as sometimes it decides not to show the upper part of the plot if I don't.