The Mathematica Journal
Departments
Feature Articles
Columns
New Products
New Publications
Classifieds
Calendar
News Bulletins
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues
Home
Download this Issue

Programming

We have already seen several aspects of the improvements in Mathematica 4 when working with arrays of machine numbers. One reason that works efficiently is that many operations such as Table and Map automatically compile their function arguments and execute them in the Mathematica virtual machine. This all happens transparently.

But another aspect of efficient programming is to have useful primitives that make it easy to express problems directly and have it work efficiently, i.e., programmer time is also a valuable commodity. Below we see some enhancements to functional and list-based programming that should make it easy to express many programs very succinctly.

Functional Programming

In Mathematica 4 there are basic extensions of the functional programming approach in NestWhile and NestWhileList. The basic idea is to make nested operations (or iterations) whose stopping criteria can be data dependent--as is the case for a While loop--available as a functional programming primitive. This frequently leads to quite compact and efficient code.

The following program adds [Graphics:../Images/index_gr_171.gif] until some element reappears.

[Graphics:../Images/index_gr_172.gif]
[Graphics:../Images/index_gr_173.gif]

It is then easy to combine this construction with other ones such as Table.

[Graphics:../Images/index_gr_174.gif]
[Graphics:../Images/index_gr_175.gif]

List Programming

The extensions to list operations include new operations such as ListConvolve, ListCorrelate, PadLeft, and PadRight, as well as extensions to existing ones like Partition. One aspect these operations have in common is that they can handle data that requires padding.

One of course naturally associates ListConvolve to filtering operations such as finite impulse response (FIR) filter, or moving average (MA) processes. This also applies to higher-dimensional signals such as the image filtering (2D) we saw earlier, and volumetric filtering (3D). But the convolution construction turns out to be remarkably applicable outside of these areas as well.

Below is an example that performs multiplication of integer sequences in base b.

[Graphics:../Images/index_gr_176.gif]

The functions IntegerDigits and FromDigits handle unpacking and packing digits back into their number data structure, including the proper treatment of carries.

[Graphics:../Images/index_gr_177.gif]
[Graphics:../Images/index_gr_178.gif]

This works just fine even for quite large numbers, in this case 100,000 digit numbers.

[Graphics:../Images/index_gr_179.gif]
[Graphics:../Images/index_gr_180.gif]
[Graphics:../Images/index_gr_181.gif]

But it is more efficient to work in a slightly larger base, in this case base [Graphics:../Images/index_gr_182.gif]. This effectively shortens the digit sequence and makes better use of the built-in arithmetic in the processor.

[Graphics:../Images/index_gr_183.gif]
[Graphics:../Images/index_gr_184.gif]

The same ideas apply to polynomial and series multiplication. Below is an example of polynomial multiplication that is quite efficient for certain types of polynomials. As can be seen, it basically mimics the number multiplication algorithm.

[Graphics:../Images/index_gr_185.gif]

In this case we have to define a function that returns a polynomial expression from its coefficient tensor.

[Graphics:../Images/index_gr_186.gif]

First a simple check that we have gotten the details right.

[Graphics:../Images/index_gr_187.gif]
[Graphics:../Images/index_gr_188.gif]
[Graphics:../Images/index_gr_189.gif]

This defines a random dense polynomial of degree [Graphics:../Images/index_gr_190.gif], and then multiplies it by itself.

[Graphics:../Images/index_gr_191.gif]
[Graphics:../Images/index_gr_192.gif]
[Graphics:../Images/index_gr_193.gif]


Converted by Mathematica      June 4, 2000

[Article Index] [Prev Page][Next Page]