Creating a Smooth Acceleration in Animation

Date: 05/09/2001 at 21:30:56
From: William Fex
Subject: 1=X-(X^(119/120)) I need to solve for X

I have a formula for the exponential increase of a number from 0 to 
the target number: 

  ((x+1)^y)-1 where y = {0, 1/120, 2/120, 3/120, ..., 120/120} 

The first answer to this is ((x+1)^y)-1 = 0 then ((x+1)^y)-1 = x, ...

This is not difficult to solve for at all. The problem arises when I 
am trying to figure out a way to set the value of X to achieve a 
specific difference between the last two sets in this problem. I am 
using this for an animation, and I want the object in the animation to 
accelerate smoothly over the course of 120 frames, and then in the 
next 120 frames to move at a constant rate of speed. I am using X to 
represent the location of the object. In the next set of frames I will 
simply move at x*y, where y = {0, 1/120, 2/120, etc.} What I need to 
know is how to determine how far I need to move in those first 120 
frames to obtain an exact speed. For this example I will seek a 
movement rate of exactly 1 unit per frame. 

I have figured out that the number I am seeking can be simplified to 
1 = X-(X^(119/120)). This if solved will tell me what X must equal in 
the formula ((x+1)^y)-1 for the difference in those last two frames 
where y = 119/120 and then y = 120/120 to be exactly 1.

HELP! I lack the math skills to understand how to solve the equation:
1 = X-(X^(119/120)). I figured out a slew of other problems on my own 
and I am largely self-taught, but my high school math never went 
beyond Algebra I and Geometry I, and my college math was minimal. This 
is for a hobby, but it is making my brain bleed! Help me Doctor Math! 
Tell me how I go about solving a monster like this. Several of my 
friends have run screaming from this problem.

Date: 05/11/2001 at 13:18:06
From: Doctor Douglas
Subject: Re: 1=X-(X^(119/120)) I need to solve for X

Hi Bill, and thanks for writing to Ask Dr. Math.

This appears to be a transcendental equation, which means that there 
is no solution that is easily expressible in terms of the functions 
that we usually encounter (say, on a calculator).

However, that does not mean that no methods exist for *computing* the 
solution. For example, as long as we have access to a calculator that 
can compute powers (y^x), we can do the following simple procedure: we 
graph the function

     f(x) = X - X^(119/120) - 1

and see where it crosses zero. We can show that for x = 1, f(x) = -1 
and for x = 50, f(50) = 50 - 50^(119/120) - 1 = +0.603. I used a 
calculator for this last computation. Since f(1) and f(50) have 
opposite signs, and since the function f is "continuous," meaning that 
its graph can be drawn as a single line without lifting the pencil 
from the paper, I know that f must equal zero somewhere for some x 
between 1 and 50. This is known as "bracketing the root."  By trying a 
few values of x on a calculator, we can focus in on a solution for x 
by making the bracket tighter and tighter. Once we have a bracket, we 
just pick a point in the middle of the interval and evaluate the value 
of f there. Either f = 0 (we're done but this is unlikely to happen) 
or f < 0 or 
f > 0. Whichever one of these latter cases occurs, it will have a sign 
opposite to one of the two function values that we started with - in 
other words, we will still have the root bracketed, but with an 
interval that is smaller. So we can do this process repeatedly to 
focus in on the root.

  f(25) = -0.3383   pick something in the middle; bisecting works well
  f(40) =  0.2109   ah, a solution is bracketed by 25 and 40
  f(35) =  0.0218   between 25 and 35, and probably much closer to 35
                      so make our next guess 33, not 30
  f(33) = -0.0523   solution is bracketed by 33 and 35
  f(34) = -0.0154   bracketed by 34 and 35
   .        .
   .        .
   .        .
 
If I keep doing this process, I obtain x = 34.415159... I verified 
this solution by plugging it back into the equation for f(x).

Note how it isn't necessary to choose the interior point to be the 
midpoint (25 is not exactly (50+1)/2, for example) but we were free to 
choose numbers that were relatively convenient. We also took a chance 
by guessing 33 rather then 30 - this kind of procedure helps save on 
the total number of function evaluations, so that we don't do too much 
work.

I hope that this shows you how we can obtain a numerical solution to 
f(x) = 0 when f is continuous. The method is not much more than trial 
and error, guessing a point and noting whether f is positive or 
negative at that point, guided by an intelligent way of determining 
the next guess. Incidentally, many sophisticated root-finding methods 
are used in mathematical computing. Some of them involve various 
enhancements for how the guessing procedure can be made more efficient 
if you know something about the function.

I hope this helps. Please write back if you have more questions about 
this.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/