MaplePrimes Posts

MaplePrimes Posts are for sharing your experiences, techniques and opinions about Maple, MapleSim and related products, as well as general interests in math and computing.

Latest Post
  • Latest Posts Feed
  • The second day of the 2005 Maple conference was another busy day at Wilfred Laurer University. The day began with an excellent keynote presentation from Dr. Richard Gran, the CEO of Mathematical Analysis Company. His talk began with him recalling his days working on the Lunar Module for the Apollo moon missions. It was quite a pleasure to see this man speak.
    I would like to give a big welcome to everyone who just found out about this site at the Maple Conference. I hope that all of you will find the site to be very useful and enjoyable to use. For those of you who are not attending the conference, it is Maplesoft's annual gathering of Maple users. This year it is taking place at Wilfred Laurier University in Waterloo, Ontario.

    A while ago, I was trying to determine the fastest way, using Maple, to compute a list of a particular sequence of integers defined by a recurrence relation. This isn't a new idea of course, but I think the exercise is a useful introduction into the various ways of coding algorithms in Maple, and why some may be better than others.

    My original example was a bit esoteric, so for simplicity I've redone it using the standard example of a recurrence relation, the Fibonacci sequence. We'll fix N, the number of Fibonacci numbers to compute, at 40000.

    > N := 40000:

    Below, we'll try to find the fastest way, in Maple, to compute a list of these numbers from scratch. Note that the speed comparisons might be specific to this machine, OS, or Maple version, and even though the runtime of most of these implementations is about the same, the fastest method at N=40000 might not be the fastest one for larger N.

    The first idea is the completely naive approach. We'll store the Fibonacci numbers in a Maple list L, step through a loop counting up the sequence, and in each loop iteration add to the list with L := [op(L), new_element].

    f1 := proc(N)
        local i, L;
        L := [1, 1];
        for i from 2 to N do
            L := [op(L), L[-2] + L[-1]];
        end do;
        L
    end proc:

    The problem with this approach is that Maple lists are not intended to be grown in this way, and each redefinition of the list L costs O(N) time, making the whole procedure O(N).

    > time(f1(N));
    31.440

    From now on we'll use only implementations that take O(N) time, and see how they compare.

    The next implementation uses a Maple table stored as a local variable of a module. We compute the sequence and assign it to table entries, and at the end generate a Maple list from these table entries. The use of tables is advantageous because tables can be dynamically grown more efficiently than lists can, but this approach has the disdvantage that the table must be completely re-traversed in the last step to generate the list.

    f2 := module()
        local ModuleApply, T;

        T := table([0=1, 1=1]);

        ModuleApply := proc(N)
            local i;
            for i from 2 to N do
                T[i] := T[i-2] + T[i-1];
            end do:
            [seq(T[i], i=0..N)]
        end proc:
    end module:

    You'll see that since this code avoids list-appending, it's quite a bit faster:

    > time(f2(N));
    1.110

    The next idea is to do essentially what we did above, but using remember tables rather than built-in Maple tables. We'll pre-populate the remember table for the utility procedure p with entries for the base cases, F0 and F1, and then build our list through recursive calls.

    f3 := module()
        local p, ModuleApply;

        p := proc(n) option remember;
            procname(n-2) + procname(n-1)
        end proc:

        p(0) := 1;
        p(1) := 1;
     
        ModuleApply := proc(N)
            [1, 1, seq(p(i), i=2..N)]
        end proc:
    end module:

    As we might expect, the computed result is pretty close (but a bit higher than) our last number.

    > time(f3(N));
    1.229

    One disadvantage of the last two approaches is that they both rely on creating an intermediate data structure of size O(N) (the table or remember table), which is promptly discarded, since what we're interested in is a list. Instead we can use a 'cache', which is a new feature of Maple 9.5, and is essentially a remember table of bounded size.

    f4 := module()
        local p, ModuleApply;

        p := proc(n) option cache;
            procname(n-2) + procname(n-1)
        end proc:

        p(0) := 1;
        p(1) := 1;

        ModuleApply := proc(N)
            [1, 1, seq(p(), i=2..N)]
        end proc:
    end module:

    It works out to be slightly slower than f3; this may be because of the time taken in garbage-collecting the information from the cache.

    > time(f4(N));
    1.459

    Next, I've tried to implement something like a cache, without actually using one. Here we have a utility procedure with two counters, which represent the last and second-last Fibonacci number respectively. The procedure updates the values and returns the appropriate one. We'll build the list with recursive calls to this procedure. Like the cache, the intermediate data structures used here are of bounded size, since there are just two of them.

    f5 := module()
        local p, n1, n2, ModuleApply;

        n1 := 1;
        n2 := 1;

        p := proc(n)
            (n1, n2) := (n2, n1+n2);
            n2;
        end proc:

        ModuleApply := proc(N)
            [1, 1, seq(p(), i=2..N)]
        end proc:
    end module:

    It's about the same speed as using the cache, which is impressive since it involves a lot more procedure calls into the procedure body than the cache example, which mostly consisted of calls into the cache.

    > time(f5(N));
    1.439

    Finally, mostly for completeness, we try to see we get by pre-allocating an Array and adding to that. Arrays can be modified inplace in O(1) time, but cannot be dynamically grown. Here we make an array of the appropriate size, fill it, then convert it to a list.

    f6 := proc(N)
        local A, i;
        A := Array(0..N, {0=1,1=1});
        for i from 2 to N do
            A[i] := A[i-2] + A[i-1];
        end do:
        convert(A, 'list')
    end proc:

    It's about as fast as the previous two examples, and has the advantage of simplicity of design. However, building the array and converting that to a list is another instance of using large intermediate data structures, which we avoided with the previous two examples.

    > time(f6(N));
    1.469

    So it looks like f2 is the winner in this very specialized contest. This probably has more to do with the quirks of this example than any difference in efficiency of the code concerned. And if minimizing intermediate memory use is the goal, then f4 or f5 would be preferable.

    See Rydberg Searching for an editor to create hyperlinks without typing html... MK

    There are two ways of directly entering math into MaplePrimes. The first is the <maple> tag. Any text between <maple></maple> tags will be interpreted as Maple syntax and be replaced with a 2D GIF image of that syntax.

    The Inbox and Private Message functionality has the potential to be very useful. Some issues: On selecting "Write a New Message", I see a blank field "To" next to a field marked "--contacts--". "--contacts--" should presumably expand to a list of users who I've marked as my contacts. However, the only way I can find to add to this list is to compose/receive mail from some user. 1) I might like to add a user to my Contacts list for future reference, without actually composing an email to this person immediately. 2) I think of 'contacts' as frequent contacts, and would like to be abl
    We're now getting into the final points. One thing that I envisioned for this site is some way for individuals to showcase themselves and if they wanted to share certain identifying and possibly fun information. Currently that section looks extremely corporate and wreaks of someone wanting spam targets.

    My suggestions are,

    1) remove telephone numbers all together
    2) keep addresses as knowing what country, city, organization etc.
    3) My job is, (choose one only):
    - technical professional in industry or government
    - professor or university staff
    - graduate student
    - undergraduat student
    One of the more interesting application areas of Maple is in the area of cryptography. A symbolic system's algebraic and integer facilities are great tools in exploring or developing ciphers. Today, I was chatting with a colleague of mine on the topic of ancient computers and at one point, I had expressed my desire to find a replica Enigma machine ... I was promptly introduced to ... http://mckoss.com/Crypto/Enigma.htm Paper Enigma Machine

    There has been active threads on easy ways to post Maple or math specific content - e.g. code snippets, good looking math, plots etc. This Web site will definitely be less effective if people are forced into cumbersome processes to put what most of us would consider to be "fundamental" information into their postings.

    Theory has it that Maple is good at producing HTML code. For the original application that it was intended - i.e. creating self-contained Web pages, it works pretty well. Can this theory be extended to cover our MaplePrimes beta application. How easy is it to use Maple as the authoring environment to express some math and to do a plot and general HTML code that is useful for MaplePrimes? 

    Just out of curiosity, are we actually intending on using the content rating tools, or are they there as part of the default Drupal installation? I ask because the rating boxes (e.g. here) take up a reasonable amount of screen space, and never seem to go away, even after one rates the page. I would expect the rating box to go away or change after I've rated something. At the moment I find the rating boxes distracting, since I'm more interested in the user-provided text.
    Well, I've been working on a units poster for some time now... Okay, so this isn't the same as some of the blogs which are currently posted, but c'est la vie. I recall thinking how close g (= 9.80665) was to π, and only now do I learn that that is more than coincidence. When the French came up with the metre, I guess they wanted something very close to three Parisian feet, and there were at least two possibilities: 1/10 000 000 the distance from the North Pole to the Equator or the length of a pendulum which has a half period of 1 s. As it turned out, they picked the former, but as both were close appropximations to the same standard, it ended up that `≈`(sqrt(g/m), pi/s), and thus, solving for g, we get that `≈`(g, pi^2).
    Hello everyone and welcome to MaplePrimes. My name is William Spaetzel and I am the guy who did most of the technical work behind this website.
    Hello everyone and welcome to MaplePrimes. My name is William Spaetzel and I am the guy who did most of the technical work behind this website.
    This is just a test
    > x <> 23!!
    >>> x^@
    Under "my account" there seems to be no easy way of listing all of my recent posts (of all types). There's only an option to list recent blogs. Most of my content are either forum posts or stories as proper blogs are not one of the default content options that I'm given. T4.
    First 265 266 267 268 269 Page 267 of 269