Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Maximizing significant digits

101 views
Skip to first unread message

Virgil

unread,
Oct 13, 2000, 3:00:00 AM10/13/00
to
In article <39e7e805$0$1593$3929...@news.execpc.com>, Dave Lyle
<dave...@execpc.com> wrote:

> Got a math story problem where the question involves determining how
> many moves it will take to move a stack of various sized disks from one
> place to another with certain constraints.
>
> It works out that for n disks, it takes (2^n)-1 moves to accomplish the
> task. The problem states n=64 and that each move takes one second, and
> asks how long it will take to move the pile.
>
> If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
> or [2^64)-1]/31536000.


Using an HP49 calculator, I find
[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.


Note that a more careful analysis will note that the average year length
is nearer to 365.24 days, when you make some allowance for leap years.
>
> 2^64 is a *big* number (1.844674407e19) <g>. Using a calculator causes
> a loss of some of the significant digits. What's the best way to
> manipulate this expression to minimize that problem?

Get a better calculator
>
> I though about expressing the denominator as 2^x, then I could subtract
> exponents before expanding. I'd need to solve 2^x=31536000 for x, and
> I'm drawing a blank on how to do that.
>
> Dave

Dave Lyle

unread,
Oct 14, 2000, 1:26:24 AM10/14/00
to
Got a math story problem where the question involves determining how
many moves it will take to move a stack of various sized disks from one
place to another with certain constraints.

It works out that for n disks, it takes (2^n)-1 moves to accomplish the
task. The problem states n=64 and that each move takes one second, and
asks how long it will take to move the pile.

If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
or [2^64)-1]/31536000.

2^64 is a *big* number (1.844674407e19) <g>. Using a calculator causes


a loss of some of the significant digits. What's the best way to
manipulate this expression to minimize that problem?

I though about expressing the denominator as 2^x, then I could subtract


exponents before expanding. I'd need to solve 2^x=31536000 for x, and
I'm drawing a blank on how to do that.

Dave


--
remove alphabet to reply

Doug Magnoli

unread,
Oct 14, 2000, 3:00:00 AM10/14/00
to
If I were doing this by, as you suggest, subtracting out the powers of 2
from num and den, I wouldn't start by wanting to know exactly x, where
2^x=n, because x won't be an integer, and here comes more uncertainty.

(By the way, to do that, you'd want to take the log(base 2) of n, which is
simply ln(n) / ln(2).)

Instead, you can start with the list of factors you have for the
denominator and pull the 2's out from there, which also allows you to see
exactly what you're doing.

60*60*24*365 = (2^2*15)^2 *(2^3 *3) * 365
= 2^7 * 15*3*365,

which doesn't get you very far, but it does demonstrate the method.

-Doug Magnoli

Stan Brown

unread,
Oct 14, 2000, 3:00:00 AM10/14/00
to
[This followup was also e-mailed to the cited author for speed.
Please follow up in the newsgroup.]

Dave Lyle <dave...@execpc.com> wrote in alt.algebra.help:

>If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
>or [2^64)-1]/31536000.

There is essentially no difference between 2^64 and 2^64-1. (The
difference is one part in 2^64, which is roughly one part in
16*10^18 since 2^10 = approx 10^3.) So you can simply drop the -1
from the numerator, compute 2^64/31536000,and you're done.

(365 is not quite the right factor for converting days to years, by
the way. When there are a large number of years, 365.25 is more
accurate, though still not exact.)

>I though about expressing the denominator as 2^x, then I could subtract
>exponents before expanding.

That would be incorrect. The error is negligible in this particular
case, but still you should not think you can simplify
(2^a - 1) / 2^b
If you divide top and bottom by 2^b you then have
(2^(a-b) - 2^(-b))
which still has two powers of 2 to contend with. However, as I say,
in this particular problem with a = 64, the difference between the
actual numerator and plain 2^64 is numerically negligible.

> I'd need to solve 2^x=31536000 for x, and
>I'm drawing a blank on how to do that.

It's a moot point in this particular problem, but the general way to
solve exponential equations is to take log of both sides. (You can
use any base, as long as you use the same base on both sides.)
2^x = 31536000
log(2^x) = log(31536000)
log(a^b) = b*log(a), so
x*log(2) = log(31536000)
x = log(31536000)/log(2)

--
Stan Brown, Oak Road Systems, Cortland County, New York, USA
http://oakroadsystems.com
FAQs and math resources: http://oakroadsystems.com/math/resource.htm
more FAQs: http://oakroadsystems.com/tech/faqget.htm

Ted Lind

unread,
Oct 14, 2000, 3:00:00 AM10/14/00
to
Just manage your numbers as you do the calculation:

[2^64)-1]/31536000
(2^64)/31536000-1/31536000

The last term can be dropped since it won't be significant enough to change
the result (it will affect the 8th decimal place), the first term can be
manipulated as follows:

=2^64/(2^7*3^3*5^3*73)
=2^57/(3^3*5^3*73)
=[2^28/(3^3*5^3*73)]*[2^29/(3^3*5^3*73)]
=[268435456/31536000]*[536870912/31536000]
=8.5120324*17.024065
=144.90939

Since you are dividing a nine digit number by an 8 digit number you will
have a result with eight significant digits. Then you multiply two eight
digit number resulting in a number with eight digit accuracy. Most
calculators will do nine digits.

"Dave Lyle" <dave...@execpc.com> wrote in message
news:39e7e805$0$1593$3929...@news.execpc.com...

Brian M. Scott

unread,
Oct 14, 2000, 3:00:00 AM10/14/00
to
On Fri, 13 Oct 2000 23:25:13 -0600, Virgil <Vm...@frii.com> wrote:

>In article <39e7e805$0$1593$3929...@news.execpc.com>, Dave Lyle
><dave...@execpc.com> wrote:
>

>> Got a math story problem where the question involves determining how
>> many moves it will take to move a stack of various sized disks from one
>> place to another with certain constraints.
>>
>> It works out that for n disks, it takes (2^n)-1 moves to accomplish the
>> task. The problem states n=64 and that each move takes one second, and
>> asks how long it will take to move the pile.
>>
>> If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
>> or [2^64)-1]/31536000.

>Using an HP49 calculator, I find


>[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.

You dropped a digit: it should be 5849_4_2417355.

>Note that a more careful analysis will note that the average year length
>is nearer to 365.24 days, when you make some allowance for leap years.

365.2422 is a very good approximation. This yields 584554529390
years, 15 hours, 18 minutes, 45 seconds (to the nearest second). Of
course this ignores changes in the length of the year, and 365.2422 is
just a hair large.

[...]

Brian M. Scott

Virgil

unread,
Oct 14, 2000, 3:00:00 AM10/14/00
to
In article <39e88c88...@enews.newsguy.com>, sc...@math.csuohio.edu
(Brian M. Scott) wrote:

> >Using an HP49 calculator, I find
> >[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.
>
> You dropped a digit: it should be 5849_4_2417355.

Quite correct, thank you.

Dave Lyle

unread,
Oct 15, 2000, 1:03:30 AM10/15/00
to
Doug Magnoli wrote:
>
> If I were doing this by, as you suggest, subtracting out the powers of 2
> from num and den, I wouldn't start by wanting to know exactly x, where
> 2^x=n, because x won't be an integer, and here comes more uncertainty.

> (By the way, to do that, you'd want to take the log(base 2) of n, which is
> simply ln(n) / ln(2).)
>
> Instead, you can start with the list of factors you have for the
> denominator and pull the 2's out from there, which also allows you to see
> exactly what you're doing.
>
> 60*60*24*365 = (2^2*15)^2 *(2^3 *3) * 365
> = 2^7 * 15*3*365,
>
> which doesn't get you very far, but it does demonstrate the method.
>
> -Doug Magnoli

Neat! I'll have to remember that method. Thanks.

And thanks to all the others that replied.

--
Dave
remove alphabet to reply

Dave Lyle

unread,
Oct 15, 2000, 1:13:41 AM10/15/00
to
Virgil wrote:
>
> Using an HP49 calculator, I find
> [2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.
>

> Get a better calculator

Looks like your HP49 has two more significant digits than this TI-83
Plus.

Thanks!

Dave Lyle

unread,
Oct 15, 2000, 1:19:05 AM10/15/00
to
Stan Brown wrote:

> It's a moot point in this particular problem, but the general way to
> solve exponential equations is to take log of both sides. (You can
> use any base, as long as you use the same base on both sides.)
> 2^x = 31536000
> log(2^x) = log(31536000)
> log(a^b) = b*log(a), so
> x*log(2) = log(31536000)
> x = log(31536000)/log(2)

Got it, thanks.

0 new messages