Posted on

Math test 1

sine, cosine, tangent…

(a^2+b^2)=a^2+2ab+b^2

 

wpmathpub

Precise evaluation, almost by inspection.

Q: What is the easiest, most fundamental way to precisely evaluate triginometric functions…almost by inspection? And how is it all related to square root?

Since: , , … what else?

Q: Would you believe that: = … (exactly) almost by inspection?

Q: How about the inverses: arcsine, arccosine, arctangent?
Do they have something to do with squaring (the inverse of square root)?

An Old Algorithm

In the mid-1950s, programmers were devising the very first math libraries for their new vacuum-tube computers. One possible technique used a clever algorithm to calculate the inverses of a certain class of functions, such as Arccosine. [1]

Arccosine Algorithm

Input = Y: -1 ≤ Y ≤ 1

X := 0; z := Y

for i := 1 to n do

if z ≥ 0 then

z := 2z2 – 1

else

z := 1 – 2z2

X := X + 2-i

Output = X = Arccos(Y)/π to ‘n’ binary digits.

Note how the only operations are add, subtract, shift, square; and no constants except 1 and 2.
Consider the deep relation to the “double-angle formula”: cos 2α = 2 cos2 α – 1

For example, evaluate: Arccos (0.471396737) = 0.0101102 π (n = 6) = 22π / 64

i

Z

X

+0.471396737

0.0000002

1

-0.555570233

0.0100002

2

+0.382683432

0.0100002

3

-0.707106781

0.0101002

4

0

0.0101002

5

-1

0.0101012

6

-1

0.010101̅1…2

-1

0.0101102

Though unique in its simplicity, some noted that this algorithm loses accuracy for some inputs (when ‘z’ nears ±1.0), and its convergence is relatively slow. [2] Also, there is no similar way to calculate cosine directly. Thus, this algorithm was eventually abandoned (though occasionally revisited [3]), and nearly forgotton with the passage of time.

A New Algorithm

In fact, the above algorithm can be reversed to produce the cosine with perfect symbolic accuracy.

Do you see why this works?

Cosine Algorithm

Input = Xn: a binary number 0.b1b2b3b4…bn000…

Y := 1.0; b0 := 0; bn+1 := 0

for i := n downto 0 do

Note: ⨁ is bitwise exclusive-OR

Output = Y = cos(π Xn) exactly!

Or symbolically, cos (11 π / 32) =

(exactly)

For example, evaluate: cos (11 π / 32) = cos (0.0101102 π) [ Xn = 11/32 = 0.0101102 (n=5) ]

i

bi

S

Y

5

1

-1

-1.0

4

1

+1

+0.0

3

0

-1

-0.70710678…

2

1

-1

-0.38268343…

1

0

-1

-0.55557023…

0

0

+1

+0.47139673…

Try it using the online spreadsheet below.

Square Root Algorithm

During an internship in 1988, my officemate was updating a drawing program when he came across some assembly code for calculating the distance between two points:

To our amazement, the square root routine simply did a few shifts, increments, subtractions in a loop.

(It credited Dr. Dobb’s Journal.) [4, 5]

Square Root Algorithm

Input = Xn: 0 ≤ Xn < 1 (‘n’ binary digits) Y := 0; R := Xn for i := 1 to n step 2 R := 4R Y := 2Y T := R – (2Y + 1) if T >= 0 then

R := T

Y := Y + 1

Output = Y = 2n/2√̅Xn

Remainder = R: Y2 + R = 2n Xn

For example, evaluate: (n = 8)

i

T

R

Y

170/256 =

0.6640625

0

1

1.65625

1.65625

1

3

1.625

1.625

3

5

-6.5

6.5

6

7

1

1

13

Y2 + R = 132 + 1 = 170 = 28 * 170/256

Hardware Implementation

The algorithms described above are particularly simple to implement in hardware, with no operation more complex than binary subtraction, and where the potential drawbacks of a software implementation evaporate.

Square Root

An n-bit square root can be implemented with a 2n-bit input using an n+2 -bit subtractor and four n-bit shift registers (plus control logic).

RootDiagramSimple.png

Cosine

The square root circuit becomes a cosine circuit by adding another shift register (angle input) and three exclusive-or gates. The first XOR creates the ‘±S’ value, combining two adjacent bits of the shifting angle value. The other two XOR gates implement the ‘±’ operation, doing a serial, 1s-complement negation of the square-root input as it shifts out from the input registers.

The square root then produces: (Where 0 ≤ T < 1, so is trivial to represent in the data lines.)

Sine

The cosine circuit can also produce the sine by trivially adding two 1-bit inverter gates as feedback around the root input registers. Then as the circuit begins its final square root iteration to produce the cosine, its input registers contain the cosine-squared. Feeding that back in as the 1s-complement negation produces 1-cos2x = sin2x. Then one additional square root iteration produces: sin(x)

Accuracy

The cosine circuit described above does lose accuracy for certain inputs. In those cases, the internal precision may need to be as high as 2n bits to produce an n-bit cosine. However, the missing bits of accuracy do not vanish. In fact, they are immediately available in the square root remainder register!

To see why, consider with remainder, such that: (exactly)

Now when , , since: and

(In other cases the remainder is not such a good extension of the square root result, although it is always better than extending a 2n-bit intermediate result by simply appending zeros.)

The combined ~2n bits of square root output then feed back into the 2n-bit input registers, as the iterations ultimately produce an n-bit cosine, which is found to be accurate to better than 1.3 in 216.

Combined Sine, Cosine, Square Root

The essence of the combined trigonometric circuit, with optimizations, looks like this:

Construction

The full trignometric processor was constructed while I was a student at BYU, and full details have been peer-reviewed and published. [6, 7]

The project included a simple Z80 interface which attached to an 80s-era Timex-Sinclair 2068.

Demonstration

A trigonometry-intensive, 3-D plotting program was implemented in Z80 assembly with both software and hardware evaluation of sine and square root. (In software, the square root used the algorithm above, but the sine used a rough CORDIC implementation.)

Here you can see the the execution, with the hardware evaluation providing an ~11X speedup:

References (PDF)

[1] D. R. Morrison, A Method for Computing Certain Inverse Functions [1956]

[2] M. V. Wilkes, D. J. Wheeler, Note on “A Method for Computing Certin Inverse Functions” [1957]

[3] J. H. Wensley, A Class of Non-Analytical Iterative Processes [1959]

[4] “68000 Restoring Square Root Routine,” Dr. Dobb’s Journal, vol. 10 #5 (May 1985) pp. 118,122

[5] “Letters: Right to Optimize [Square Root],” Dr. Dobb’s Journal, vol. 11 #8 (Aug. 1986) pp. 12-14,81-85

[6] R. E. Fowkes, Minimal Hardware Algorithms for Trigonometric Functions [Wescon, Nov. 19-21, 1991]

[7] R. E. Fowkes, Hardware Efficient Algorithms for Trigonometric Functions [IEEE Trans. Comp., Feb. 1993]

Cosine: Cell by Cell

Posted on

The Muppet Movie

“A frog and a bear, seeing America!”

-Fozzie Bear, The Muppet Movie

There was a time, not too long ago, when the world was swept up in full-on Muppet Mania. Adorable felt-and-foam constructions brought to convincing life by an array of artisans first overtook TV airwaves, then graduated to vinyl and celluloid. The excitement peaked with the release of the critters’ initial big screen adventure on June 22nd, 1979. The Muppet Movie will return to theaters across the country to commemorate that 40th birthday this summer via Fathom Events on July 25th and 30th. So what better time than now to wax poetic about the crowning and singular cinematic achievement that is The Muppet Movie?

According to Christopher Finch’s excellent, comprehensive illustrated Jim Henson biography Jim Henson: The Works, Henson’s Muppets were commissioned to grace the silver screen by The Muppet Show producer Lord Lew Grade following the variety TV show’s successful second season (it would ultimately last for five seasons and 120 episodes). After years of interacting with rotating guest hosts on sets, The Muppet Show was a somewhat magical evolution for Kermit the Frog (Henson), Fozzie Bear (Frank Oz), Miss Piggy (Oz again), Gonzo (Dave Goelz), and all their cloth pals. A bear, a frog, and all their colorful compatriots would indeed see America, traversing much more realistic terrain with impressive ease.

Muppet performers Henson, Oz, Goelz, Jerry Nelson, and Richard Hunt took their critters out of the studio and into a bevy of real-world locations… convincingly! From Kermit riding a bicycle to Kermit strumming a banjo on a boat surrounded completely by water (remember, his puppeteer Henson had to manipulate Kermit’s motions, several years before the advent of computer-generated imagery), to Gonzo taking a 100-foot balloon ride, to a Busby Berkeley-channeling Miss Piggy musical number, The Muppet Movie served as a special showcase for a special batch of creature creators.

Our tale opens on a private screening in World Wide Studios (actually CBS Studio Center in Studio City), as a frazzled Kermit the Frog fetes a showing of the meat of the story, a movie-within-a-movie that Kermit concedes is “sort of approximately how” the Muppets got together. We discover Kermit with said banjo singing mournfully atop a log in a Floridian forest swap. The artistry of this in-camera effect is almost immediately overshadowed by just how sweetly compelling our puppet hero Kermit is. We stop fretting about the craftsmanship of the story and just buy it, hook, line and sinker by about the middle of the show-stopping opening number, “The Rainbow Connection.” Hot-shot Hollywood talent agent Bernie (Dom Deluise), struck by Kermit’s musical bonafides, recommends Kermit respond to an open casting call from World Wide Studios seeking “Frogs wishing to become Rich and Famous.”

Kermit quickly hops on his bicycle and sets off for Hollywood. Yes, it’s a spectacular effect, and no, you don’t think about just how tough it must have been to achieve until long after the movie’s over. Almost immediately, Kermit is beset by the sadistic restaurateur Doc Hopper (Charles Durning) and his hapless assistant Max (Austin Pendleton). Hopper instantly tries to recruit Kermit to act as the spokes-frog for his burgeoning fried frog legs fast food franchise. Sure, Hopper will also need to fry Kermit’s legs to seal the deal, but Hopper sees that as a small personal price for Kermit to pay. When Kermit denies him outright, Hopper and Max doggedly pursue Kermit for the rest of the picture.

After losing his bike in a construction mishap, Kermit encounters Fozzie Bear in the appropriately named dump El Sleezo Café. Kermit and Fozzie soon team up, and Kermit has upgraded his transit to Fozzie’s 1951 Bullet Nose Studebaker Commander. The duo soon finds Dr. Teeth and The Electric Mayhem rocking out in a church during a very meta exchange, and the band gives the Studebaker a psychedelic makeover. Kermit and Fonzie’s entourage quickly expands to include enterprising “plumbing artiste” Gonzo and his beloved Camilla the Chicken (Jerry Nelson), Bogen County Beauty Pageant champ and aspiring actress Miss Piggy, and committed bachelor bar pianist Rowlf The Dog (also Henson). As they continue struggling to evade Hopper, Max, and their growing stable of intimidating frog assassins, the Muppets’ modes of transit shift several times, and they run into many a delightful celebrity cameo en route to fame and fortune.

The joyfully rambling road picture effectively builds to an ultimate showdown pitting Kermit and his friends against Hopper and his hired guns in a deserted Western town. Following Kermit’s impassioned plea that Hopper cease his cruel designs on Kermit’s legs for his restaurant chain, we are for a moment convinced that Kermit has appealed to an untapped human decency somewhere deep in Hopper’s core. And though that would be emotionally satisfying, there would be absolutely nothing believable about that sudden character shift.

Doc Hopper’s irredeemability here somehow rings sadly true. Sometimes, evil is just evil, and there’s nothing you can do about it but hope a temporarily-enlarged mad drummer intercedes on your behalf. Electric Mayhem percussionist Animal (Oz again) proves to be just the Muppet for the job when he pops out of a nearby bar, after guzzling an invention from Bunsen and Beaker that briefly expands him to gargantuan proportions. Animal terrifies Hopper and his goons into a full, permanent retreat.

Do the Muppets make it to Hollywood and Vine? Do they find a way past Lew Lord’s pesky, animal hair-averse assistant (Cloris Leachman) to ink a Standard Rich And Famous Contract? Of course they do, and you won’t be able to wipe a dumb grin off your face when the gang celebrates with their show-stopping musical finale, “The Magic Store.”

About those celebrity cameos. The Muppet Movie is positively littered with grade-A talent, from obvious Muppet inspirations Edgar Bergen and Charlie McCarthy to ’70s comedy staple Madeleine Kahn. This author’s personal favorites: James Coburn’s barfly El Sleezo owner, Carol Kane’s very responsive Myth (“Yes?”), and, of course, Steve Martin’s appropriately named Insolent Waiter (“Would you like to smell the bottle cap?”).

There’s one more cameo that deserves special mention on this website. For those who don’t remember, though, I won’t spoil the identity of Hollywood studio bigwig Lew Lord. Lord stands as The Muppet Movie’s own Wizard of Oz at the end of these puppet dreamers’ rainbow. Let’s just say that it’s someone who never really got along with Hollywood studio bigwigs themselves.

Everyone has their favorite Muppet. Kermit is a fairly boilerplate choice, but I can’t in good conscience pick anyone else. Kermit can be meek and put-upon, but he remains winningly dogged in all his pursuits, and ultimately leads his creature consorts where they want to go with conviction, kindness and intelligence. He’s also a big fan of ponds. Suffice it to say, if he ran for president in 2020, he’d get my vote. My runner-up circa The Muppet Movie? Crazy Harry (Nelson again), the heavily caffeinated pyromaniac muppet. Sometimes, that disruptive anarchic itch feels pretty good to scratch, too.

The Muppet Movie was a smash hit in its day. It grossed $65.2 million domestically — equivalent to $234 million in 2019 ticket prices, according to Box Office Mojo, which would make it the 6th-best attended movie this year. The film’s music was so great that it merited two Academy Award nominations — Best Adaptation Score (no longer a category) and Best Original Song (“Rainbow Connection”). It was robbed in both instances. But then again, it’s almost cooler not to win, isn’t it? “The Muppet Movie” connected with critics as well as audiences, netting a very favorable 74% rating on Metacritic, a more accurate critical review aggregate than the somewhat-inflated Rotten Tomatoes. The two biggest movie critics in the universe at that time, Gene Siskel and Roger Ebert, numbered among its biggest champions.

Directed by Muppet outsider James Frawley, produced by Henson, and written by Muppet Show scribes Jack Burns and Jerry Juhl, The Muppet Movie succeeds as a movie primarily because of some core elements that might feel passé to studio bigwigs today. It exhibits a uniquely tactile charm predicated on old-fashioned, clearly cheesy puppet creations. It employs a cleverly threadbare plot that harkens back to the Hope/Crosby/Lamour road pictures, with a sprinkling of a Western ensemble piece. This simple, familiar framework gives performers and puppeteers alike plenty of room to riff. It openly explores the relative darkness of its completely irredeemable chief villain’s frog legs spokesperson plot. And perhaps best of all, The Muppet Movie disarms us with a cheerfully ambiguous meta-awareness to engage and involve viewers in its tirelessly excitable “let’s put on a show” ethos.

Another standout here is The Muppet Movie‘s gorgeous soundtrack, featuring eminently hummable, banjo-heavy Grammy-winning compositions from Paul Williams (a hit songsmith throughout the 1970s, most famous in front of the camera as Little Enos Burdette in the first Smokey and the Bandit) and Kenneth Ascher (who also orchestrated string arrangements for several John Lennon and Yoko Ono albums). Standouts include the opening Kermit showstopper “Rainbow Connection” and the Miss Piggy’s lovestruck paean to Kermit “Never Before, Never Again,” but “Movin’ Right Along,” the winning Kermit-Fozzie duet, is the chipper adventure track that wedged itself into this viewer’s heart permanently upon first listen.

A small TFH connection: according to a 2011 interview with the New York Times, Trailers From Hell Guru John Landis happened to visit the set during the film’s 250-puppet-strong closing wide shot, and was commissioned to puppeteer Grover. He was joined in the pit by a pre-Pee Wee’s Big Adventure Tim Burton, then a puppeteer’s union member.