TweetFollow Us on Twitter

Background TCL
Volume Number:9
Issue Number:12
Column Tag:TCL Workshop

A Piece of Apple Pi

Background processing with TCL

By Malcolm H. Teas, Rye, New Hampshire

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

About the author

Malcolm Teas has been programming the Macintosh for five years. He’s active with object programming in TCL and also uses C with Think and MPW. He lives, works, and consults from his house on the seacoast of New Hampshire.

I needed a project to test the new Think C version, since I have an interest in number theory, the project I picked was a Π calculation program. Most similar programs take over the machine while they’re at work. I wanted this one (just to keep life interesting) to optionally calculate Π in the background and let other applications continue. As the Mac doesn’t have preemptive multitasking, background applications only get time as permitted from the foreground application and vice versa. So, when we program time-intensive tasks, we’ve got to be nice to other software that may be running. The approach I took here is to let the user decide if this application should hog the system or not by setting an option in a menu. The default is to not hog.

To do this, I break the calculation up into a number of steps. The steps are implemented by a subclass of a TCL Chore object. This work is done at idle event time indirectly by the Dawdle() method of the bureaurocrats. The amount of CPU time that the calculation takes is the same if it’s done in the background or if the application hogs the system. However, the amount of time to the user is significantly longer if the work’s done in the background. This is due to the overhead of the time through the toolbox getting the idle event to run the calculation code. In addition, the calculation code is done in small steps and interspersed with other applications, etc. In the hog mode, it never leaves the calculation code at all but other apps don’t get CPU time.

Backgrounding is best for an application that’s got pre-calculation to do or can intersperse work with user input. As humans are so slow compared to the computer, the imbalance of speed can be put to good use this way.

Designing a chore for background processing

There are a couple of issues for chore-based background work. First, the chore has to be handled or know where to get all the information it needs for it’s processing. Second, if it’s work that gets completed that something else depends on, the chore has to be able to signal work complete. Last, chores need to be disposed of. One thing at a time.

In my case, my CPiChore class is a subclass of the CChore class. You’ll have to subclass the CChore class too as the standard class does nothing. The only method in CChore is the Perform() method (and of course those methods it inherits from CObject). My CPiChore subclass overrides the Perform() and Dispose() methods. It also has two new methods InitChore() and GetTicks() for setting the necessary data and getting information.

The InitChore() method takes all the necessary data as parameters. If I’d had a lot of data I could’ve passed a structure with the data loaded into it. However, as I only had four items, that seemed overkill for this project. Another alternative would’ve been for the chore to ask the necessary objects for the relevant data.

InitChore() takes the number of digits of Π to calculate, a pointer to the document object, and two flags to determine if the calculation should be timed and if hog mode is on. This data is stored locally. Note that the flags are stored in the object, but the document and the number of digits are stored in global variables that are defined and declared in the CPiChore.cp file. This makes them local to that file. The document object CAppPiDoc declares the CPiChore in it’s include file (CAppPiDoc.h). As a short-cut, I included the CAppPiDoc.h file in the CPiChore.cp file, and declared a global “document”. This means that I don’t have to type-cast as often when I use the “document” variable. The “Digits” variable is where the numDigits value is put. As this Π calculation code is ported, I didn’t convert all the calculation code to methods, instead, I left them and their global data in this CPiChore.cp file as straight C functions and data.

Perform() is the function in a chore that actually does the work. It’s called by the Idle() function in CApplication which is called every time an idle event happens. TCL considers an idle event to occur when we either receive a null event or a mouse-moved event. Note that if you’re doing background processing, you want null events while you’re app is in the background. To get them, the “Background null events” flag in the Size resource must be set. Use the SIZE flags popup in the Set Project Type dialog to do this.

The Idle() function also does some other things like check memory and do the Dawdle() method in the CBureaucrat object. Idle() runs through the chain of command to call all the Dawdle() methods there. It then runs through the list of chores to call Perform() on all the chores in the list.

When it gets to the Perform() method in CPiChore, CPiChore uses a stage counter to figure out what’s been done and what to do next. Basically, this determines and remembers what step it’s on. CPiChore uses the Machin algorithm to calculate Π (see the sidebar). The last step in the calculation stops the count of the time and tells the CAppPiDoc object that the chore is done by calling PiDone() in the document with the result of the calculation as it’s parameter.

The document gets the time the calculation took, sets flags for the state of the calculation and sends the result to the pane for display. The next time and idle event happens and the document’s Dawdle() method is called, the chore will be disposed of. This approach to deallocating the chore is known as lazy management of memory. It has the advantage that, as the Dawdle() method is called all the time, it’s more sure in deallocating the chore. The completion and the deallocation are in independent routines.

The pane to display this information isn’t a standard text edit pane. Text edit can only handle information up to around 30K of text characters. It’s easy to generate a value of Π that takes more space that this. I subclassed CPanorama to make a pane that just displayed a lot of text for this application. In addition, this CPiPane object also knows how to translate the digit numbers to text characters and how to display the time information too.

Implementation details

All the key user actions are handled through the DoCommand() method of the CAppPiDoc object. The one exception is the about box which is handled in the application’s DoCommand() method.

The number of digits is set in a dialog box that I use the regular TCL dialog classes to run. The DoCommand() method extracts the digit count from the dialog before it’s disposed. Although Symantec’s documentation states that the dialog objects must be subclassed to be really useful, I didn’t find the need to do that with the number of dialog view objects that know about the format and range of information. In this case, I used an integer text dialog view object that was told, via the template, what range of numbers to accept. Then, I use the FindViewByID() method to get that object and extract the now-conditioned value.

The time and hog (or “faster”) commands just toggle their values. In the UpdateMenus() method, these values are used to determine if those menu items are checked or not.

The start command is the important one. If the Π calculation chore is running, then this item is labeled “Stop”. If selected, it cancels and disposes of the chore. If the chore isn’t running, it starts it using the currently set number of digits and the timing and faster flags. It then assigns the chore to the application, this puts the chore in the chore list to be processed on an idle event. The chore will stay in the list until removed.

Once the chore is in the list, then the Perform() method is called with every idle event. If the faster or hog mode is on, then the Perform() method doesn’t return until the calculation is complete. Otherwise, it does one step and returns.

When the calculation is complete, the Perform() method calls the PiDone() method in the document which hands the result data off to the pane for display with the pane’s SetContent() method. This result data looks like the other data used in the calculation. It’s an array of character, but I use the characters as small integers. Actually, there’s a fair amount of wasted space as the integers range from 0-9. The calculation is carried out in decimal and there are custom routines to handle multiple place arithmetic.

The SetContent() method disposes any previous pointer to data (the data is held as pointers due to the ported code) and converts the data to characters for display. It does this by simply adding the integer value of the character zero to each number in the array.

When the Draw() method for the pane is called (it’s called automatically when the pane needs to be refreshed or when Refresh() is called), it sets the font and size of the text to draw. Draw() then creates a header line, draws it, skips down a little and draws the characters for Π. To do the drawing of the text, Draw() calls a routine called DrawWrapText() to wrap the text at the margins correctly.

DrawWrapText() takes parameters to the text, it’s size, and the margin, line information and whether or not to force a margin. This latter is similar to typing the return key to force a new line.

Listing:  CPiChore.cp
/*
 CPiChore
 Written and copyright by Malcolm H. Teas 1993.
 All rights reserved.
 
*/

#include "CAppPiDoc.h"

/*
 * Global variables
 */
int   Sign, 
 Zero, 
 Digits, 
 Pass,  /* two passes */
 Exp, /* exponent for divide */
 Divide;
static int constant[3]={0,25,239};

CAppPiDoc *document;
 
/*
 * These character arrays represent the digits for extended
 * precision arithmatic. (These may need to be int on 
 * some machines).
 */
#define DIGIT char
DIGIT *Power, *Term, *Result;

void copy (void);
void init(void);
void divi(register DIGIT *array);
void sub (void);
void add (void);

void CPiChore::Perform (long *maxSleep)
{
 long start;
 
 if (timeCalc)
 start = TickCount ();
 
 do  {
 switch (stage)  {
 case 0:
 init ();
 stage++;
 break;
 
 case 1:
 copy();
 Divide = Exp;
 divi(Term);
 if ( Sign > 0 ) 
 add();
 if ( Sign < 0 ) 
 sub();
 Exp = Exp + 2;
 Sign *= -1;
 Divide = constant[Pass];
 divi(Power);
 if (Pass == 2) 
 divi(Power);
 if (Zero == 0)
 stage++;
 break;
 
 case 2:
 Pass++;
 init ();
 stage++;
 break;
 
 case 3:
 copy();
 Divide = Exp;
 divi(Term);
 if ( Sign > 0 ) 
 add();
 if ( Sign < 0 ) 
 sub();
 Exp = Exp + 2;
 Sign *= -1;
 Divide = constant[Pass];
 divi(Power);
 if (Pass == 2) 
 divi(Power);
 if (Zero == 0)
 stage++;
 break;
 
 case 4:
 if (timeCalc)  {
 ticks += TickCount() - start;
 timeCalc = false;
 }
 document->PiDone (Result);
 stage++;
 break;
 
 case 5:
 break;
 }
 }  while (faster && stage != 5);
 
 if (timeCalc)
 ticks += TickCount() - start;
}

void CPiChore::InitChore (long numDigits, CDocument *doc, 
 Boolean timeIt, Boolean faster)
{
 stage = 0;
 Pass = 1;
 document = (CAppPiDoc *) doc;
 timeCalc = timeIt;
 ticks = 0;
 this->faster = faster;
 
 Digits = numDigits;
 FailNIL (Power = (char *) NewPtr (numDigits + 1));
 FailNIL (Term = (char *) NewPtr (numDigits + 1));
 FailNIL (Result = (char *) NewPtr (numDigits + 1));
}

long CPiChore::GetTicks (void)
{
 return ticks;
}

void CPiChore::Dispose (void)
{
 DisposPtr (Power);
 DisposPtr (Term);

 inherited::Dispose (); 
}

void add (void)
{
 register DIGIT *r, *t;
 register int sum, carry = 0;
    
 r = Result + Digits;
 t = Term + Digits;
 
 while( r >= Result )
 {
 sum = *r + *t + carry;
 carry = 0;
 if( sum >= 10 )
 {
 sum -= 10;
 carry++;
 }
 *r-- = sum;
 --t;
 }
}
 
void sub (void)
{
 register DIGIT *r, *t;
 register int diff, loan = 0; 
 
 r = Result + Digits;
 t = Term + Digits;
 
 while( r >= Result )
 {
 diff = *r - *t - loan;
 loan = 0;
 if( diff < 0 )
 {
 diff += 10;
 loan++;
 }
 *r-- = diff;
 --t;
 }
}
 
void divi(register DIGIT *array)
{
 register DIGIT *end;
 register int quotient, residue, digit = 0;
 
 Zero = 0;
 
 for( end = array + Digits; array <= end; )
 {
 digit    += *array;
 quotient =  digit / Divide;
 residue  =  digit % Divide;
 
 if((Zero !=0) || ((quotient+residue) != 0)) 
 Zero = 1;
 else 
 Zero = 0;
 
 *array++ = quotient;
 digit = 10 * residue;
 }
}
 
void init(void)
{
 register DIGIT *p, *t, *r, *end;
 
 p = Power;
 t = Term;
 r = Result;
 end = Power+Digits;
 
 while( p <= end )
 {
 *p++ = 0;
 *t++ = 0;
 
 if (Pass == 1) 
 *r++ = 0;
 }
 
 *Power = 16 / (Pass * Pass);
 
 if( Pass == 1 ) 
 {
 Divide = 5;
 }
 else
 {
 Divide = 239;
 }
 
 divi(Power);
 Exp = 1;
 Sign = 3 - (2 * Pass);
}
 
void copy (void)
{
 register DIGIT *t, *p, *end;
 
 t = Term;
 p = Power;
 end = Term + Digits;
 
 while (t <= end)
 {
 *t++ = *p++;
 }
}

How to calculate Π

The number Π in it’s simplest form, is the ratio of the circumference of a circle to that circle’s diameter. It’s an irrational number so it can’t be represented exactly by a ratio, or fraction, between two integers. As decimal numbering systems are essentially another way of expressing a fraction (i.e. the number 2.5 is actually the fraction 25/10), then Π, expressed as a decimal number, has an infinite number of places. A good reference for Π calculations is the book “History of Π” by Petr Beckmann.

The Π calculation algorithms work by interating over an approximation to Π. Each iteration, or time through the algorithm, the accuracy of the Π estimate increases. We say that we’re calculating Π, but we’re actually calculating an approximation to it. John Wallis, a sixteenth-century mathemetician, discovered a series of fractions, that when multiplied together result in Π. These are two ways to write Wallis’ product:

While this works fine, it’s also quite slow to converge or increase in accuracy, each fraction added doesn’t increase the accuracy very much. The Apple Π program in the article uses the Machin algorithm which converges much faster. It sums more complex fractions to speed up the process. More recently, mathemeticians using elliptical integrals discovered the holy grail of Π calculations: an algorithm, that while quite complex, doubles the number of accurate digits of Π for each iteration.

I ported the Machin algorithm from a version by Bryan Costales, who in turn ported it from a version by Robert Bishop. The algorithm is based on the equation:

[This is a Taylor expansion of 16 * Arctan(1/5) - 4 * Arctan(1/239). Tech. Ed.]

I use arrays of digits to implement the numbers and have written my own routines to do the arithmetic with these numbers. The calculation above is broken down into a number of steps. A step is done each time through the idle loop in the application.

Some have claimed that calculating Π to ever increasing numbers of digits (the record is around 40 million digits currently) is unecessary and not useful. However, when companies install a new supercomputer, this kind of calculation can be used for testing as it repeats intensive CPU work.

Number theorists use the results of long Π calculations to analyze the characteristics of the number, and through it, other similar numbers. Since number theory is a fundamental branch of mathematics that’s used in cryptography and computer theory this work may shed light on some aspects of mathematics that can be of practical use. Besides, it’s fun.

 
AAPL
$116.47
Apple Inc.
+0.16
MSFT
$47.98
Microsoft Corpora
-0.72
GOOG
$537.50
Google Inc.
+2.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Cobook 3.0.7 - Intelligent address book....
Cobook Contacts is an intuitive, engaging address book. Solve the problem of contact management with Cobook Contacts and its simple interface and powerful syncing and integration possibilities.... Read more
StatsBar 1.9 - Monitor system processes...
StatsBar gives you a comprehensive and detailed analysis of the following areas of your Mac: CPU usage Memory usage Disk usage Network and bandwidth usage Battery power and health (MacBooks only)... Read more
Cyberduck 4.6 - FTP and SFTP browser. (F...
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Evernote 6.0.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
calibre 2.11 - Complete e-library manage...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Herald 5.0.1 - Notification plugin for M...
Note: Versions 2.1.3 (for OS X 10.7), 3.0.6 (for OS X 10.8), and 4.0.8 (for OS X 10.9) are no longer supported by the developer. Herald is a notification plugin for Mail.app, Apple's Mac OS X email... Read more
Firetask 3.7 - Innovative task managemen...
Firetask uniquely combines the advantages of classical priority-and-due-date-based task management with GTD. Stay focused and on top of your commitments - Firetask's "Today" view shows all relevant... Read more
TechTool Pro 7.0.6 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PhotoDesk 3.0.1 - Instagram client for p...
PhotoDesk lets you view, like, comment, and download Instagram pictures/videos! (NO Uploads! / Image Posting! Instagram forbids that! AND you *need* an *existing* Instagram account). But you can do... Read more

Latest Forum Discussions

See All

Ubisoft Gives Everyone Two New Ways to E...
Ubisoft Gives Everyone Two New Ways to Earn In-Game Stuff for Far Cry 4 Posted by Jessica Fisher on November 21st, 2014 [ permalink ] | Read more »
Golfinity – Tips, Tricks, Strategies, an...
Dig this: Would you like to know what we thought of being an infinite golfer? Check out our Golfinity review! Golfinity offers unlimited ways to test your skills at golf. Here are a few ways to make sure your score doesn’t get too high and your... | Read more »
Dark Hearts, The Sequel to Haunting Meli...
Dark Hearts, The Sequel to Haunting Melissa, is Available Now Posted by Jessica Fisher on November 21st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Meowza! Toyze Brings Talking Tom to Life...
Meowza! | Read more »
Square Enix Announces New Tactical RPG f...
Square Enix Announces New Tactical RPG for Mobile, Heavenstrike Rivals. Posted by Jessica Fisher on November 21st, 2014 [ permalink ] With their epic stories and gorgeous graphics, | Read more »
Quest for Revenge (Games)
Quest for Revenge 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: The great Kingdom of the west has fallen. The gods ignore the prayers of the desperate. A dark warlord has extinguished... | Read more »
Threadz is a New Writing Adventure for Y...
Threadz is a New Writing Adventure for You and Your Friends Posted by Jessica Fisher on November 21st, 2014 [ permalink ] In the tradition of round-robin storytelling, | Read more »
SteelSeries Stratus XL Hardware Review
Made by: SteelSeries Price: $59.99 Hardware/iOS Integration Rating: 4 out of 5 stars Usability Rating: 4.5 out of 5 stars Reuse Value Rating: 4.25 out of 5 stars Build Quality Rating: 4.5 out of 5 stars Overall Rating: 4.31 out of 5 stars | Read more »
ACDSee (Photography)
ACDSee 1.0.0 Device: iOS iPhone Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Capture, perfect, and share your photos with ACDSee. The ACDSee iPhone app combines an innovative camera, a powerful photo... | Read more »
ProTube for YouTube (Entertainment)
ProTube for YouTube 2.0.2 Device: iOS Universal Category: Entertainment Price: $1.99, Version: 2.0.2 (iTunes) Description: ProTube is the ultimate, fully featured YouTube app. With it's highly polished design, ProTube offers ad-free... | Read more »

Price Scanner via MacPrices.net

CEA Study Finds More People Recycling Electro...
A new study by the Consumer Electronics Association (CEA) finds that electronics recycling receives the continued and growing support of consumers. According to the CEA,s Recycling and Reuse Study,... Read more
15″ 2.2GHz Retina MacBook Pro on sale for $17...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale today for $1749. Shipping is free, and B&H charges NY sales tax only. B&H will also include free copies of Parallels Desktop... Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the new 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available... Read more
21-inch 1.4GHz iMac on sale for $979, save $1...
B&H Photo has the new 21″ 1.4GHz iMac on sale for $979.99 including free shipping plus NY sales tax only. Their price is $120 off MSRP. B&H will also include free copies of Parallels Desktop... Read more
13-inch 1.4GHz/256GB MacBook Air on sale for...
B&H Photo has lowered their price on the 13″ 1.4GHz/256GB MacBook Air to $1059.99 including free shipping plus NY sales tax only. Their price is $140 off MSRP, and it’s the lowest price for this... Read more
Save up to $400 with Apple refurbished 2014 1...
The Apple Store has restocked Apple Certified Refurbished 2014 15″ Retina MacBook Pros for up to $400 off the cost of new models. An Apple one-year warranty is included with each model, and shipping... Read more
New 13-inch 1.4GHz MacBook Air on sale for $8...
 Adorama has the 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. B&H Photo has the 13″ 1.4GHz/128GB MacBook... Read more
Apple Expected to Reverse Nine-Month Tablet S...
Apple and Samsung combined accounted for 62 percent of the nearly 36 million branded tablets shipped in 3Q 2014, according to early vendor shipment share estimates from market intelligence firm ABI... Read more
Stratos: 30 Percent of US Smartphone Owners t...
Stratos, Inc., creator of the Bluetooth Connected Card Platform, has announced results from its 2014 Holiday Mobile Payments Survey. The consumer survey found that nearly one out of three (30 percent... Read more
2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has lowered their price on the new 1.4GHz Mac mini to $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC)- Retail S...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager, *Apple* Financial Services...
**Job Summary** Apple Financial Services (AFS) offers consumers, businesses and educational institutions ways to finance Apple purchases. We work with national and Read more
*Apple* Store Leader Program - College Gradu...
Job Description: Job Summary As an Apple Store Leader Program agent, you can continue your education as you major in the art of leadership at the Apple Store. You'll Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.