mm-74
===
what type the evlution equation is ? hyperbolic,
parabolic or> elliptical? ?ite difference method is rather
easy to understandand> realize. and discrete scheme depend on
type of your equation. so you> shouldr be careful to select
the scheme. > Actually, my case is a little bit complicated.
It's about a nonlinearevolution equation (e.g KdV, nonlinear
Schrodinger equation).
===
> Third, sqrt((double)(n*n)) is
exact> because sqrt is accurate to 1 ulp on your machine.>
> This is really the core of my original question. How do
they> do that? Someone else has already suggested that
there's> something better than Newton's algorithm.
Perhaps
it's> related to the old long-division algorithm that I
vaguely> remember from elementary school. Do you know the
details?> Intel Pentium processors and their predecessors,
the x86/x87 chips,> have ?g point square root
instructions that produce the> correctly rounded square root
of any single or double precision> ?g point number. The
algorithm is an implementation of the> method that used to be
taught in high school, modi?d for binary> arithmetic. I'm not
a hardware designer by any means, but I understand> that it is
a small modi?ation to the division algorithm.And you are very
correct. Back when I taught computermaintenance, there was
exactly one gate differencebetween div and sqrt. It had to do
with swapping twobits of the partial something prior to the
next step.
===
This question seems to resurface every few
years; Here is that ?elementary school' algorithm which many
of us weretaught.It is of arbitrary precision; i.e. limited
only by your patienceand/or your machine.Any questions,
please let me
know.TomCee**************************************************
*****************************This method for square roots is
EXACT for the number of digits thatyou havethe patience to use
it to.To view this ?e properly, convert it/view it with
a'non-proportional'font (eg Courier New in
Windows).This
method was formerly taught in primary school, but the
algorithmseemsto be ?getting lost'
today!!!-----------------------------------------------------
------------------------------------------------------------
-------------------------------------To ?d the square root
of any number to any number of
digits:******************************************************
**********************(This algorithm looks like long
division, but a bit more tedious)Write down the
number:1234567890.Starting at the decimal point and working
to the left, separate thenumberinto groups of two:12 34 56 78
90.leave lots of room to the left: 12 34 56 78 90Add some
notation (pretend these added lines are solid):
| 12 34 56 78 901. What is the largest
number squared that will subtract from the?stgroup?(It is
obviously 3 here)Square this number and perform the
subtraction: 3 | 12 34 56 78 90 -9 ___
3(This sequence of digits above the bar will be referred to
as the ?toprow'.)2. Drop down the next group of two digits: 3
| 12 34 56 78 90 | -9 | ___ | 3 343. Double
the top row and bring this doubled value down to the
left,(we'll call this the left row) leaving a placeholder for
a lesssigni?antdigit: 3 | 12 34 56 78 90 |
-9 | ___ 6_| 3 344. Now, we need to ?d the one digit such
that the product of thisdigitandthe current left row with
this digit appended is just less than theresultofthe last
subtraction. Put this digit in the placehoder and append itto
thetop row.( i.e. in this particular case, the digit is 5,
since 5*65<334, but6*66>334)Perform this multiplication and
subtraction:So we now have: 35 | 12 34 56 78
90 | -9 | ___ 65| 3 34 3 25 95. Loop starting at step 2
until you have achieved the desiredprecision.(continuing the
process so you can see the result develop:) 35
| 12 34 56 78 90 | -9 | ___ 65| 3 34 | 3 25
| Step 2: 9 56 35 | 12 34 56 78 90 | -9
| ___ 65| 3 34 | 3 25 | Step 3: 70_| 9 56Step 4: Next
digit is 1 since 1*701<956, but 2*702>956) 351
| 12 34 56 78 90 | -9 | ___ 65| 3 34 | 3 25
| 701| 9 56 | 7 01 | | 2 55continuing on: 351
| 12 34 56 78 90 | -9 | ___ 65| 3 34 | 3 25
| 701| 9 56 | 7 01 | 702_| 25578 3513
| 12 34 56 78 90 | -9 | ___ 65| 3 34 | 3 25
| 701| 9 56 | 7 01 | 7023| 25578 21069 _ 4509
3513 | 12 34 56 78 90 | -9 | ___ 65| 3 34 |
3 25 | 701| 9 56 | 7 01 | 7023| 25578 | 21069 |
_ 7026_| 450990 35136 | 12 34 56 78 90 |
-9 | ___ 65| 3 34 | 3 25 | 701| 9 56 | 7 01 | 7023|
25578 | 21069 | _ 70266| 450990 421596 __ 29394.00so,
at this point, to an approximation, sqrt(1234567890) is
35136.You are only limited by your patience as to how many
digits yourequire.Thomas Chrapkiewicz
06ap98-------------------------------------------------------
---------------------> Third, sqrt((double)(n*n)) is
exact> because sqrt is accurate to 1 ulp on your machine.>
> This is really the core of my original question. How do
they> do that? Someone else has already suggested that
there's> something better than Newton's algorithm.
Perhaps
it's> related to the old long-division algorithm that I
vaguely> remember from elementary school. Do you know the
details?
===
|> This question seems to resurface every few
years; |> |> Here is that ?elementary school' algorithm which
many of us were|> taught.|> |> It is of arbitrary precision;
i.e. limited only by your patience|> and/or your machine.|>
|> This method was formerly taught in primary school, but the
algorithm|> seems to be ?getting lost' today!!!Yes, but the
real question is why it ever WAS taught!It always was a
damn-fool method for hand calculation, though ofsome
theoretical interest. There are at least 3 better
methodssuitable for hand use or mental arithmetic. I have no
idea whyit was preferred, except that it is ?elementary' in
the sense thatit doesn't use calculus.But, considering that
both binary chop and linear interpolationare ancient, and
suitable for using in your head, that is a feebleexcuse. The
method you describe should be taught in undergraduatecourses
and not before!Nick Maclaren.
===
>|> This question seems to
resurface every few years; >|>|> Here is that ?elementary
school' algorithm which many of us were>|> taught.>|>|> It
is of arbitrary precision; i.e. limited only by your
patience>|> and/or your machine.>|>|> This method was
formerly taught in primary school, but the algorithm>|> seems
to be ?getting lost' today!!!>>Yes, but the real question is
why it ever WAS taught!It was taught because it was LESS
INTIMIDATING even if it was considerably more complicated and
error prone.I once taught an introductory Computer Science
class which includedmixed radix arithmetic. I soon had a
student show up in my of?esaying that he was hopelessly lost
with mixed radix arithmetic.I agreed and asked him to try
something much simpler. So he didthe calculation of the
travel time where both departure and arrivalwere given to the
second. Easily done and even well explained by the student. So
I then pointed out that he had just done a mixedradix
subtraction with the obvious radices. He could not get out of
my of?e fast enough after that.So mixed radix was very
dif?ult but subtracting time was familiar and easy. You
?ure out the difference.>It always was a damn-fool method
for hand calculation, though of>some theoretical interest.
There are at least 3 better methods>suitable for hand use or
mental arithmetic. I have no idea why>it was preferred,
except that it is ?elementary' in the sense that>it
doesn't
use calculus.>>But, considering that both binary chop and
linear interpolation>are ancient, and suitable for using in
your head, that is a feeble>excuse. The method you describe
should be taught in undergraduate>courses and not
before!>Nick Maclaren.
===
|>|> |>|> This method was
formerly taught in primary school, but the algorithm|>|>
seems to be ?getting lost' today!!!|>|>Yes, but the real
question is why it ever WAS taught!|> |> It was taught
because it was LESS INTIMIDATING even if it was |>
considerably more complicated and error prone.Grrk. I have
SERIOUS dif?ulty in believing that. And, yes, Iwas taught it
and ended up with a respectable mathematical degree.It
intimidated me and completely baf?e other students!I can
witness that it was widespread for students in the 1950s
toINVENT binary chop or interpolation to solve problems that
weregiven to them in the form of that elementary square root
function.I did it, and have met several others who did.|> So
mixed radix was very dif?ult but subtracting time was
familiar |> and easy. You ?ure out the difference.Oh, yes, I
take the point. Mixed radix wasn't a major issue inthe UK,
given the requirement to work out the cost of 3 tons,7
hundredweight, 11 pounds and 6 ounces of something at 2
pounds,13 shillings and 5 pence 3 farthings a stone. Some
people neverwere happy with that, so we decimalised :-)But I
don't see that being relevant here, as elementary geometrywas
taught before long division, and binary chop is a very
simpleand natural geometric technique.Nick Maclaren.
===
This method was formerly taught in primary school,
but the algorithm>|>|> seems to be ?getting lost'
today!!!>|>>|>Yes, but the real question is why it ever
WAS taught!>|>|> It was taught because it was LESS
INTIMIDATING even if it was >|> considerably more complicated
and error prone.>>Grrk. I have SERIOUS dif?ulty in believing
that. And, yes, I>was taught it and ended up with a
respectable mathematical degree.>It intimidated me and
completely baf?e other students!>>I can witness that it
was widespread for students in the 1950s to>INVENT binary
chop or interpolation to solve problems that were>given to
them in the form of that elementary square root function.>I
did it, and have met several others who did.>>|> So mixed
radix was very dif?ult but subtracting time was familiar >|>
and easy. You ?ure out the difference.>>Oh, yes, I take the
point. Mixed radix wasn't a major issue in>the UK, given the
requirement to work out the cost of 3 tons,>7 hundredweight,
11 pounds and 6 ounces of something at 2 pounds,>13 shillings
and 5 pence 3 farthings a stone. Some people never>were happy
with that, so we decimalised :-)>>But I don't see that being
relevant here, as elementary geometry>was taught before long
division, and binary chop is a very simple>and natural
geometric technique.But in some sequencing algebra would be
completed before geometry was introduced. My recollection is
that the manual square root wasin the weird and wonderful
fancier things algebra could do at the level of peeking at
advanced things in junior high school (grades 7, 8 and 9)
while geometry was for high school (grades 10, 11 and 12)
where it was treated as practice for being careful and
rigourous for those who did not take Latin which was no
longer taught in any case.So the issue of which things are
natural and which things areintimidating is quite context
dependent.A friend's wife could not use a pantograph with
corkscrew bottleopener until she was given a lesson in
geometry and mechanical advantage. After that the device
stated to work!>Nick Maclaren.
===
>>But in some sequencing
algebra would be completed before geometry >was introduced.
My recollection is that the manual square root was>in the
weird and wonderful fancier things algebra could do at the
>level of peeking at advanced things in junior high school
(grades >7, 8 and 9) while geometry was for high school
(grades 10, 11 and >12) where it was treated as practice for
being careful and >rigourous for those who did not take Latin
which was no longer >taught in any case.That is VERY recent in
the UK, and I am pretty sure that it is fairlyrecent in most
countries. In the traditional (Euclidean) teaching,algebra
was started a long time after geometry. Latin was
mandatoryfor me, and Euclidean geometry was effectively so
until I was 15.I started geometry at 7, but algebra not until
about 10.And, if you have started algebra ?st, I don't see
the problem withusing binary chop. It isn't much harder to
explain algebraicallyand is fairly widely used by people with
no mathematical trainingwhatsoever.>So the issue of which
things are natural and which things are>intimidating is quite
context dependent.That is very true.>A friend's wife could not
use a pantograph with corkscrew bottle>opener until she was
given a lesson in geometry and mechanical >advantage. After
that the device stated to work!A nice example! I have seen
that effect quite a few times, and haveencountered it
myself.Nick Maclaren.
===
> It always was a damn-fool method
for hand calculation, though of> some theoretical interest.
There are at least 3 better methods> suitable for hand use or
mental arithmetic.If you only want to know the ?st 3 or 4
digits then the elementaryschool algorithm doesn't seem bad
to me at all. You suggest binarychop and interpolation, but
binary chop is worse (the elementary schoolalgorithm is
effectively decimal chop), and interpolation requires youto
do long division. Newton's algorithm in the variant without
divisionmight be better, except that you have to do more
multiplication.
===
|> |> It always was a damn-fool method
for hand calculation, though of|> some theoretical
interest. There are at least 3 better methods|> suitable
for hand use or mental arithmetic.|> |> |> If you only want
to know the ?st 3 or 4 digits then the elementary|> school
algorithm doesn't seem bad to me at all. You suggest binary|>
chop and interpolation, but binary chop is worse (the
elementary school|> algorithm is effectively decimal chop),
and interpolation requires you|> to do long division.
Newton's algorithm in the variant without division|> might be
better, except that you have to do more multiplication.The
advantage of binary chop is that it requires much
less'housekeeping' and hence the student is less
likely to
getconfused. It is also easy to make it self-correcting, in
thesense that you will spot many stupid errors before going
toofar. This makes it MASSIVELY better for that level of
studentand for mental arithmetic.You do NOT need to do
signi?ant long division either forinterpolation or any form
Newton-Raphson. In both cases, youneed to do only an
approximate division on the error, and itdoesn't matter if it
is slightly inaccurate. In the form o?terpolation that I was
taught (and use), you are typicallyusing it for an n-fold
chop (e.g. one decimal digit).I know of NO practical
advantage of the elementary schoolalgorithm over either of
the latter methods. In both cases, ifyou do the division of
the correction to only one decimal place,you end up with a
moderately self-correcting decimal chop. Ifthe expense of the
extra (full-length) multiplications matters,then you should
use them in their normal (proper) form.Nick Maclaren.
===
I
wish to learn how to deploy ?ed point math (Using integers
to representFractions) .Are they any interesting tutorials /
links that someone can provide.My target is going to be a
microcontroller ?ally.For example how does one do math with
DSP ?ter coeffecients like0.000012121 with a ?ed point
system using a microcontroller.
===
|> I wish to learn how to
deploy ?ed point math (Using integers to represent|>
Fractions) .|> Are they any interesting tutorials / links
that someone can provide.|> My target is going to be a
microcontroller ?ally.|> For example how does one do math
with DSP ?ter coeffecients like|> 0.000012121 with a ?ed
point system using a microcontroller.Look up pretty well any
pre-1950 book on numerical computation.The keyword to look
for is scaling.Nick
Maclaren.
===
http://www.optimization-online.org/>>about Fuzzy
Logic, Fuzzy Systems or fuzzy DSS used in Supply
Chain>Managment?>I've been looking in the web for quite a
while but I only ?d>abstracts...>>any help would be
appreciated.
===
Just wondering in what cases QL
factorization would be used.And what's the relationship
between QR and QL, say, given QR,how to obtain QL
accordingly?
===
> Just wondering in what cases QL
factorization would be used.>And what's the relationship
between QR and QL, say, given QR,>how to obtain QL
accordingly?>> there is a discussion of this in Parletts book
on the symmetric eigenvalue problem. QR goes from column one
to column n and within a column (using Givens
transformations) from bottom up. QL just reverses everything,
going from column n to column one and top down in a column.
but you cannot rewrite a QR as a QL. QL is to be preferred
for socalled graded matrices there the elemnets grow
drastically along the diagonalsuch that the large elements
appear in the right lower corner.hthpeter
===
> Just
wondering in what cases QL factorization would be used.> And
what's the relationship between QR and QL, say, given QR,>
how to obtain QL accordingly?QL is QR applied to the matrix
where the column ordering is reversed (then shuf?
resulting Q and R correctly). You have to do the reordering
beforehand, since from QR for A you cannot get QL for A
easily. For most applications, the ordering does not matter;
in case of sparsity one probably would like to have a more
general reordering. So what is implemented is just a matter
of taste (and tradition).Arnold NeumaierX-Received: (from
approve@localhost) by support1.mathforum.org
(8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) id
hBADQSJ17476;
===
1) Can you ?d explicitely elements of the
matrixA=Product[{{1,x},{x^{3k},1}} ,{k,1,n}]i.e.A= |1 x| |1
x| |1 x| |1 1| |x^3 1| ... |x^{3n} 1| ?2) Expand
A=Product[1-x^k,{k,1,n}]?
===
I am Looking for all good
information or programs on Maximum EntropySpectral
Analysis.
===
> I am Looking for all good information or
programs on Maximum Entropy> Spectral Analysis.> Try
this:http://www.astr.ucl.ac.be/help/user_guide/mesa/
mesa.htmMarple's book (included source code) on spectral
analysis might cover this topic also.OUP
===
Dear All,I would
be interested in ?ding the algorythm of factor analysis in
php.Who might help me ?T.Y.
===
Here is a question on
orthogonal projection. LetP be the orthogonal projection onto
the range of A.Is this projection unique? And if A*A^+ is the
orthogonalprojection onto range of A? A^+ is the
Moore-Penrosepseudoinverse of A.