> what type the evlution equation is ? hyperbolic, parabolic or > elliptical? finite 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 nonlinear evolution 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 floating point square root instructions that produce the > correctly rounded square root of any single or double precision > floating point number. The algorithm is an implementation of the > method that used to be taught in high school, modified for binary > arithmetic. I'm not a hardware designer by any means, but I understand > that it is a small modification to the division algorithm. And you are very correct. Back when I taught computer maintenance, there was exactly one gate difference between div and sqrt. It had to do with swapping two bits 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 were taught. It is of arbitrary precision; i.e. limited only by your patience and/or your machine. Any questions, please let me know. TomCee **************************************************************************** *** This method for square roots is EXACT for the number of digits that you have the patience to use it to. To view this file 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 algorithm seems to be 'getting lost' today!!! ---------------------------------------------------------------------------- -------------------------------------------------------------------------- To find 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 the number into groups of two: 12 34 56 78 90. leave lots of room to the left: 12 34 56 78 90 Add some notation (pretend these added lines are solid): ________________ | 12 34 56 78 90 1. What is the largest number squared that will subtract from the first group? (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 'top row'.) 2. Drop down the next group of two digits: 3 ________________ | 12 34 56 78 90 | -9 | ___ | 3 34 3. 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 less significant digit: 3 ________________ | 12 34 56 78 90 | -9 | ___ 6_| 3 34 4. Now, we need to find the one digit such that the product of this digit and the current left row with this digit appended is just less than the result of the last subtraction. Put this digit in the placehoder and append it to the top row. ( i.e. in this particular case, the digit is 5, since 5*65<334, but 6*66>334) Perform this multiplication and subtraction: So we now have: 35 ________________ | 12 34 56 78 90 | -9 | ___ 65| 3 34 3 25 ____ 9 5. Loop starting at step 2 until you have achieved the desired precision. (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 56 Step 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 55 continuing 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.00 so, at this point, to an approximation, sqrt(1234567890) is 35136. You are only limited by your patience as to how many digits you require. 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 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 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 included mixed radix arithmetic. I soon had a student show up in my office saying that he was hopelessly lost with mixed radix arithmetic. I agreed and asked him to try something much simpler. So he did the calculation of the travel time where both departure and arrival were given to the second. Easily done and even well explained by the student. So I then pointed out that he had just done a mixed radix subtraction with the obvious radices. He could not get out of my office fast enough after that. So mixed radix was very difficult but subtracting time was familiar and easy. You figure 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 difficulty in believing that. And, yes, I was taught it and ended up with a respectable mathematical degree. It intimidated me and completely baffled the 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 difficult but subtracting time was familiar |> and easy. You figure 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. 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 difficulty in believing that. And, yes, I >was taught it and ended up with a respectable mathematical degree. >It intimidated me and completely baffled the 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 difficult but subtracting time was familiar >|> and easy. You figure 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 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. So the issue of which things are natural and which things are intimidating is quite context dependent. 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! >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 fairly recent in most countries. In the traditional (Euclidean) teaching, algebra was started a long time after geometry. Latin was mandatory for 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 first, I don't see the problem with using binary chop. It isn't much harder to explain algebraically and is fairly widely used by people with no mathematical training whatsoever. >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 have encountered 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 first 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. ==== |> |> 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 first 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 get confused. It is also easy to make it self-correcting, in the sense that you will spot many stupid errors before going too far. This makes it MASSIVELY better for that level of student and for mental arithmetic. You do NOT need to do significant long division either for interpolation or any form Newton-Raphson. In both cases, you need to do only an approximate division on the error, and it doesn't matter if it is slightly inaccurate. In the form of interpolation that I was taught (and use), you are typically using it for an n-fold chop (e.g. one decimal digit). I know of NO practical advantage of the elementary school algorithm over either of the latter methods. In both cases, if you do the division of the correction to only one decimal place, you end up with a moderately self-correcting decimal chop. If the 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 fixed 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 finally. For example how does one do math with DSP filter coeffecients like 0.000012121 with a fixed point system using a microcontroller. ==== |> I wish to learn how to deploy fixed 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 finally. |> For example how does one do math with DSP filter coeffecients like |> 0.000012121 with a fixed 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 find >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 so called graded matrices there the elemnets grow drastically along the diagonal such that the large elements appear in the right lower corner. hth peter ==== 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 shuffle the 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 Neumaier X-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 find explicitely elements of the matrix A=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 Entropy Spectral 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.htm Marple's book (included source code) on spectral analysis might cover this topic also. OUP ==== Dear All, I would be interested in finding the algorythm of factor analysis in php. Who might help me ? T.Y. ==== Here is a question on orthogonal projection. Let P be the orthogonal projection onto the range of A. Is this projection unique? And if A*A^+ is the orthogonal projection onto range of A? A^+ is the Moore-Penrose pseudoinverse of A.