Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #57543 > unrolled thread
| Started by | krishna.myneni@ccreweb.org |
|---|---|
| First post | 2017-04-18 04:49 -0700 |
| Last post | 2017-04-26 01:55 -0700 |
| Articles | 20 on this page of 78 — 16 participants |
Back to article view | Back to comp.lang.forth
real to rational number krishna.myneni@ccreweb.org - 2017-04-18 04:49 -0700
Re: real to rational number lehs <skydda.barnen@gmail.com> - 2017-04-18 06:48 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 19:09 -0700
Re: real to rational number lehs <skydda.barnen@gmail.com> - 2017-04-18 22:53 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-19 04:43 -0700
Re: real to rational number rickman <gnuarm@gmail.com> - 2017-04-19 15:41 -0400
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-19 13:03 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-20 17:26 +0000
Re: real to rational number hughaguilar96@gmail.com - 2017-04-20 14:29 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-19 23:44 +0000
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-19 19:30 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-20 17:08 +0000
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-20 11:46 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-21 09:47 +0000
Re: real to rational number lehs <skydda.barnen@gmail.com> - 2017-04-20 20:49 -0700
Re: real to rational number rickman <gnuarm@gmail.com> - 2017-04-19 15:36 -0400
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-20 18:44 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-18 07:06 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 19:17 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-18 19:45 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 19:57 -0700
Re: real to rational number anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-04-19 05:35 +0000
Re: real to rational number hughaguilar96@gmail.com - 2017-04-18 23:42 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-19 04:53 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-19 11:32 -0700
Re: real to rational number minforth@arcor.de - 2017-04-18 08:23 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 19:24 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-18 19:48 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 20:01 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-18 19:39 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 19:56 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-19 00:41 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-19 04:48 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-19 11:30 -0700
Re: real to rational number albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-04-20 20:15 +0200
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-20 15:23 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-20 18:52 -0700
Re: real to rational number Pablo Hugo Reda <pabloreda@gmail.com> - 2017-04-18 19:58 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-18 20:05 -0700
Re: real to rational number Pablo Hugo Reda <pabloreda@gmail.com> - 2017-04-19 05:30 -0700
Re: real to rational number Pablo Hugo Reda <pabloreda@gmail.com> - 2017-04-19 05:35 -0700
Re: real to rational number Pablo Hugo Reda <pabloreda@gmail.com> - 2017-04-19 05:41 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-19 19:39 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-19 23:16 +0000
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-19 19:42 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-20 17:15 +0000
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-20 15:11 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-20 15:49 -0700
Re: real to rational number Alex <alex@rivadpm.com> - 2017-04-21 00:20 +0100
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-20 18:49 -0700
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-21 03:18 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-21 18:39 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-21 18:46 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-21 21:55 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-22 08:33 -0700
Re: real to rational number Paul Rubin <no.email@nospam.invalid> - 2017-04-22 13:35 -0700
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-24 00:58 -0700
Re: real to rational number minforth@arcor.de - 2017-04-24 01:08 -0700
Re: real to rational number minforth@arcor.de - 2017-04-23 02:28 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-21 18:43 -0700
rationalising reality, was Re: real to rational number Jan Coombs <jenfhaomndgfwutc@murmic.plus.com> - 2017-04-22 10:28 +0100
Re: rationalising reality, was Re: real to rational number Mark Wills <markwills1970@gmail.com> - 2017-04-22 02:33 -0700
Re: real to rational number krishna.myneni@ccreweb.org - 2017-04-20 16:22 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-20 22:02 -0700
Re: real to rational number Julian Fondren <julian.fondren@gmail.com> - 2017-04-21 00:12 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-21 09:55 +0000
Re: real to rational number hughaguilar96@gmail.com - 2017-04-25 10:52 -0700
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-29 03:16 +0000
Re: real to rational number "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-21 09:52 +0000
Re: real to rational number lehs <skydda.barnen@gmail.com> - 2017-04-21 05:35 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-21 19:05 -0700
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-24 01:14 -0700
Re: real to rational number Cecil Bayona <cbayona@cbayona.com> - 2017-04-24 11:31 -0500
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-25 00:52 -0700
Re: real to rational number hughaguilar96@gmail.com - 2017-04-24 11:43 -0700
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-25 00:35 -0700
Re: real to rational number The Beez <the.beez.speaks@gmail.com> - 2017-04-25 01:09 -0700
Re: real to rational number minforth@arcor.de - 2017-04-26 01:55 -0700
Page 1 of 4 [1] 2 3 4 Next page →
| From | krishna.myneni@ccreweb.org |
|---|---|
| Date | 2017-04-18 04:49 -0700 |
| Subject | real to rational number |
| Message-ID | <d34926ea-ca84-4918-aa2f-82ebb21c6470@googlegroups.com> |
Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! https://rosettacode.org/wiki/Convert_decimal_number_to_rational However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents r = -sqrt(2/(3^3*7)). When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. Incidentally, here is Forth code to compute Wigner 3j symbols -- it is somewhat limited in the range of usable angular momentum quantum numbers, though. ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg.4th and accompanying test code, ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg-test.4th Krishna
[toc] | [next] | [standalone]
| From | lehs <skydda.barnen@gmail.com> |
|---|---|
| Date | 2017-04-18 06:48 -0700 |
| Message-ID | <ca01c066-3b47-4138-8ff2-558bea6d1db8@googlegroups.com> |
| In reply to | #57543 |
Den tisdag 18 april 2017 kl. 13:49:31 UTC+2 skrev krishna...@ccreweb.org: > Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! > > https://rosettacode.org/wiki/Convert_decimal_number_to_rational > > However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). > > This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents > > r = -sqrt(2/(3^3*7)). > > When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. > > Incidentally, here is Forth code to compute Wigner 3j symbols -- it is somewhat limited in the range of usable angular momentum quantum numbers, though. > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg.4th > > and accompanying test code, > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg-test.4th > > Krishna To find an algorithm, shouldn't there be a "norm" of some kind? What is to prefer: small a and b or small difference or what?
[toc] | [prev] | [next] | [standalone]
| From | krishna.myneni@ccreweb.org |
|---|---|
| Date | 2017-04-18 19:09 -0700 |
| Message-ID | <d9c00413-adf9-4d5f-a342-2b0e436b733a@googlegroups.com> |
| In reply to | #57547 |
On Tuesday, April 18, 2017 at 8:48:13 AM UTC-5, lehs wrote: > Den tisdag 18 april 2017 kl. 13:49:31 UTC+2 skrev krishna...@ccreweb.org: > > Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! > > > > https://rosettacode.org/wiki/Convert_decimal_number_to_rational > > > > However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). > > > > This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents > > > > r = -sqrt(2/(3^3*7)). > > > > When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. ... > To find an algorithm, shouldn't there be a "norm" of some kind? What is to prefer: small a and b or small difference or what? I'm not sure if I understand your question regarding a "norm". There is a unique "a" and "b" which will yield the closest rational number to "r". One assumes the fraction is in simplified form. For the case of the Wigner 3j symbols, one can restrict the primes included to those from 2 through 19 (this range will cover angular momentum numbers of up to 4). Now, this gives us 8 primes, and their powers may be restricted to the range -4 to +4. The product of the 8 primes, each with a choice of 9 integral powers (including 0), forms our search space for expressing the |r| value as the fraction "a"/"b". However, we should also be able to use the value of |r|, which is between 0 and 1, to restrict the search space. Krishna
[toc] | [prev] | [next] | [standalone]
| From | lehs <skydda.barnen@gmail.com> |
|---|---|
| Date | 2017-04-18 22:53 -0700 |
| Message-ID | <8c2f9ac1-9fb9-4dc4-a43e-66f50ea2b838@googlegroups.com> |
| In reply to | #57565 |
I thought the float value represented some kind of measurement with an error, but if the float is regarded as a rational a/b=N/10^n then isn't it only to divide N and 10^n with their greatest common divisor d? a=N/d and b=10^n/d If there is an intervall and a/b is known to be in this intervall one has to know more. In your case the limitations of the primes and exponents is further conditions such that not any float will have a solution at all. Or am I missunderstanding?
[toc] | [prev] | [next] | [standalone]
| From | krishna.myneni@ccreweb.org |
|---|---|
| Date | 2017-04-19 04:43 -0700 |
| Message-ID | <4203a8d4-bd7f-45c4-8552-e6c916e85ee4@googlegroups.com> |
| In reply to | #57580 |
On Wednesday, April 19, 2017 at 12:53:44 AM UTC-5, lehs wrote: > I thought the float value represented some kind of measurement with an error, but if the float is regarded as a rational > > a/b=N/10^n > > then isn't it only to divide N and 10^n with their greatest common divisor d? > > a=N/d and b=10^n/d > Not exactly, since the last significant digit of our value, r, is rounded. For example, try the gcd procedure with the example, r = 7.61904761904762e-02 If you attempt gcd(761904761904762, 10^17), you will get 2, and that does not give you the simple fraction. > If there is an intervall and a/b is known to be in this intervall one has to know more. In your case the limitations of the primes and exponents is further conditions such that not any float will have a solution at all. Or am I missunderstanding? You are not misunderstanding the problem. One way to visualize it is to consider the solution space as the lattice of points in the first quadrant of the Cartesian grid, with "a" taking on integer values along the y-axis, and "b" taking on the values along the x-axis. We exclude the points which fall on the y-axis, since these represent r = inf. Now, given the restriction, |r| = a/b <= 1, we can cut the solution space in half, by only considering those lattice points which fall along or below the diagonal, y = x. Given the value of |r|, we should be able to restrict the solution space further. In the 3j symbol problem, we may use problem-domain specific knowledge, when the solutions for a restricted range of quantum numbers, e.g. for j <= 4, |r| can only take on values which are a product of restricted multiples of a range of restricted primes. That reduces the search space to a finite set of lattice points; however, it is not the same as finding the rational number for arbitrary finite-precision |r|, even with the restriction |r| <= 1. Krishna
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-04-19 15:41 -0400 |
| Message-ID | <od8ebi$531$1@dont-email.me> |
| In reply to | #57592 |
On 4/19/2017 7:43 AM, krishna.myneni@ccreweb.org wrote: > On Wednesday, April 19, 2017 at 12:53:44 AM UTC-5, lehs wrote: >> I thought the float value represented some kind of measurement with an error, but if the float is regarded as a rational >> >> a/b=N/10^n >> >> then isn't it only to divide N and 10^n with their greatest common divisor d? >> >> a=N/d and b=10^n/d >> > > Not exactly, since the last significant digit of our value, r, is rounded. For example, try the gcd procedure with the example, > > r = 7.61904761904762e-02 > > If you attempt gcd(761904761904762, 10^17), you will get 2, and that does not give you the simple fraction. > >> If there is an intervall and a/b is known to be in this intervall one has to know more. In your case the limitations of the primes and exponents is further conditions such that not any float will have a solution at all. Or am I missunderstanding? > > You are not misunderstanding the problem. One way to visualize it is to consider the solution space as the lattice of points in the first quadrant of the Cartesian grid, with "a" taking on integer values along the y-axis, and "b" taking on the values along the x-axis. We exclude the points which fall on the y-axis, since these represent r = inf. > > Now, given the restriction, |r| = a/b <= 1, we can cut the solution space in half, by only considering those lattice points which fall along or below the diagonal, y = x. Given the value of |r|, we should be able to restrict the solution space further. > > In the 3j symbol problem, we may use problem-domain specific knowledge, when the solutions for a restricted range of quantum numbers, e.g. for j <= 4, |r| can only take on values which are a product of restricted multiples of a range of restricted primes. That reduces the search space to a finite set of lattice points; however, it is not the same as finding the rational number for arbitrary finite-precision |r|, even with the restriction |r| <= 1. I don't understand all of the language you are using, but there are an infinite number of integers and the solution can be found arbitrarily close to any real value by finding larger value integers. To my understanding there is *no* single solution unless you restrict the magnitude of the integers you use. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2017-04-19 13:03 -0700 |
| Message-ID | <87mvbcdv1u.fsf@nightsong.com> |
| In reply to | #57605 |
rickman <gnuarm@gmail.com> writes: > I don't understand all of the language you are using, but there are an > infinite number of integers and the solution can be found arbitrarily > close to any real value by finding larger value integers. To my > understanding there is *no* single solution unless you restrict the > magnitude of the integers you use. There's two questions being conflated: 1) given a floating point number x, find the smallest pair of integers a,b such that a/b == x to the same precision that x is given in. 2) given an irrational number x, find rational approximations that are as close as possible to x given their size. E.g. for pi, the approximants are 3/1, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317, 312689/99532, 833719/265381, 1146408/364913, etc. Both of these are done with the continued fraction algorithm that I posted. It helps if you have bignum arithmetic for this sort of thing.
[toc] | [prev] | [next] | [standalone]
| From | "Rudy Velthuis" <newsgroups@rvelthuis.de> |
|---|---|
| Date | 2017-04-20 17:26 +0000 |
| Message-ID | <xn0koyp1p8hjbbs006@nntp.aioe.org> |
| In reply to | #57606 |
Paul Rubin wrote: > rickman <gnuarm@gmail.com> writes: > > I don't understand all of the language you are using, but there are > > an infinite number of integers and the solution can be found > > arbitrarily close to any real value by finding larger value > > integers. To my understanding there is no single solution unless > > you restrict the magnitude of the integers you use. > > There's two questions being conflated: > > 1) given a floating point number x, find the smallest pair of integers > a,b such that a/b == x to the same precision that x is given in. That is what I thought too, but apparently he means "mathematical reals", not "computer floating point numbers". -- Rudy Velthuis http://www.rvelthuis.de "In law a man is guilty when he violates the rights of another. In ethics he is guilty if he only thinks of doing so." -- Immanuel Kant
[toc] | [prev] | [next] | [standalone]
| From | hughaguilar96@gmail.com |
|---|---|
| Date | 2017-04-20 14:29 -0700 |
| Message-ID | <82d8f3aa-1d58-4b96-bc75-074bf0c5652b@googlegroups.com> |
| In reply to | #57606 |
On Wednesday, April 19, 2017 at 1:03:27 PM UTC-7, Paul Rubin wrote:
> rickman <gnuarm@gmail.com> writes:
> There's two questions being conflated:
>
> 1) given a floating point number x, find the smallest pair of integers
> a,b such that a/b == x to the same precision that x is given in.
>
> 2) given an irrational number x, find rational approximations that are
> as close as possible to x given their size. E.g. for pi, the
> approximants are 3/1, 22/7, 333/106, 355/113, 103993/33102,
> 104348/33215, 208341/66317, 312689/99532, 833719/265381,
> 1146408/364913, etc.
>
> Both of these are done with the continued fraction algorithm that I
> posted. It helps if you have bignum arithmetic for this sort of thing.
You don't need bignum arithmetic for this sort of thing, and using it will result in an unduly slow program.
You just need to be able to do a division at twice the precision that you want your result to be. Your resulting ratio is for use in ordinary Forth arithmetic and this doesn't use bignums:
-------------------------------------------------------------------------
\ The following are some ways of approximating pi, all of which were derived from the CF.4th program:
: pi* ( s -- s-result ) \ signed single-precision
1068966896 340262731 */ ;
: upi* ( u -- u-result ) \ unsigned single-precision
3618458675 1151791169 u*/ ;
: dpi* ( d -- d-result ) \ signed double-precision
1068966896 340262731 m*/ ;
: udpi* ( ud -- ud-result ) \ unsigned double-precision
3083975227 1963319607 ut*/ d2* ;
\ Note that UDPI* multiplies by pi/2 and then multiplies the result by 2.
\ This trick provides better precision sometimes.
[toc] | [prev] | [next] | [standalone]
| From | "Rudy Velthuis" <newsgroups@rvelthuis.de> |
|---|---|
| Date | 2017-04-19 23:44 +0000 |
| Message-ID | <xn0koxx1g85snxm005@nntp.aioe.org> |
| In reply to | #57565 |
krishna.myneni@ccreweb.org wrote: > On Tuesday, April 18, 2017 at 8:48:13 AM UTC-5, lehs wrote: > > Den tisdag 18 april 2017 kl. 13:49:31 UTC+2 skrev > > krishna...@ccreweb.org: > > > Rosetta Code has a number of entries for code to converting a > > > (computer representation) of a real number into a rational > > > number, or to the nearest expressible fraction, a/b, where both a > > > and b are integers. There is even a Forth entry! > > > > > > https://rosettacode.org/wiki/Convert_decimal_number_to_rational > > > > > > However, it seems like many of the algorithms expressed there are > > > brute force searches, and don't make use of the fundamental > > > theorem of arithmetic to find the suitable integers a and b > > > (though the code which uses library functions may do so). > > > > > > This particular problem has been in the back of my mind for some > > > time, and it is one that comes up from time to time. For example, > > > in the quantum physics of angular momentum, the Wigner 3-j > > > symbols are real numbers between zero and one, expressible as > > > +/-sqrt(a/b), and if one computes the quantities as real numbers, > > > it would be nice to find (a/b) in an efficient manner. In tables > > > of these symbols, the rational number a/b is expressed as a > > > series of powers of prime numbers and a sign term, e.g. -1 [1 -3 > > > 0 -1] represents > > > > > > r = -sqrt(2/(3^3*7)). > > > > > > When the finite representation of the real value is given, say to > > > double precision, a smart algorithm to find a and b, or the prime > > > powers representation would be handy. The real to rational code > > > is certainly useful, but I think the algorithms should be able to > > > take advantage of the fact that |r| <= 1. It's an interesting > > > inversion problem. > ... > > To find an algorithm, shouldn't there be a "norm" of some kind? > > What is to prefer: small a and b or small difference or what? > > I'm not sure if I understand your question regarding a "norm". There > is a unique "a" and "b" which will yield the closest rational number > to "r". Since a real is a (finite) floating point number, probably a double precision (64 bit) IEEE-754 binary floating point number, the absolutely *closest* approximation is simply the significand as integer divided by the appropriate power of 2, because that CONVERSION is exact. Even if the real is a decimal representation like 1.234, then the *best* approximation is 1234/1000. But generally, people want 0.33333333333333 to be turned into something like 1/3 and not into 33333333333333/100000000000000. That is probably what lehs means: what is the maximum number of digits (or bits) in the dividend, or what is the maximum difference in digits (or bits) between dividend or divisior, or what is the minimum or maximum epsilon used for such a conversion? In other words, how do you define the "best" appproximation (what norms do you use), if you consider the fact that neither decimal nor binary representations can always properly represent rational numbers. Or, if you want to use continued fractions, how many levels deep do you go before you quit, etc.? -- Rudy Velthuis http://www.rvelthuis.de "I hit him to get his attention. I shot him to calm him down. I killed him to reason with him." -- Henry Rollins
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2017-04-19 19:30 -0700 |
| Message-ID | <87inlzerp1.fsf@nightsong.com> |
| In reply to | #57614 |
"Rudy Velthuis" <newsgroups@rvelthuis.de> writes: > Since a real is a (finite) floating point number, By a "real" I meant a mathematical real like 1/pi, not a computer floating point number. > Or, if you want to use continued fractions, how many levels deep do you > go before you quit, etc.? When you decide that the approximation is close enough, or that the fraction has gotten too ugly.
[toc] | [prev] | [next] | [standalone]
| From | "Rudy Velthuis" <newsgroups@rvelthuis.de> |
|---|---|
| Date | 2017-04-20 17:08 +0000 |
| Message-ID | <xn0koyom18gwo2d002@nntp.aioe.org> |
| In reply to | #57623 |
Paul Rubin wrote: > "Rudy Velthuis" <newsgroups@rvelthuis.de> writes: > > Since a real is a (finite) floating point number, > > By a "real" I meant a mathematical real like 1/pi, not a computer > floating point number. Then I don't quite understand it. If you already have a mathematical real, then what is the problem? > > > Or, if you want to use continued fractions, how many levels deep do > > you go before you quit, etc.? > > When you decide that the approximation is close enough, or that the > fraction has gotten too ugly. That is probably one of the possible "norm"s lehs refers to. -- Rudy Velthuis http://www.rvelthuis.de "Be tolerant of the human race. Your whole family belongs to it -- and some of your spouse's family too." -- Anonymous.
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2017-04-20 11:46 -0700 |
| Message-ID | <87wpaedii7.fsf@nightsong.com> |
| In reply to | #57646 |
"Rudy Velthuis" <newsgroups@rvelthuis.de> writes: > Then I don't quite understand it. If you already have a mathematical > real, then what is the problem? You want to find a rational approximation to your mathematical real. E.g. suppose your real is pi. You could use 31/10 as an approximation, but it turns out 22/7 is closer. If you want even better, 355/113 is extremely close. How do you find these fractions? You could do a brute force search through possible denominators, but there's a much faster algorithm using continued fractions that I posted.
[toc] | [prev] | [next] | [standalone]
| From | "Rudy Velthuis" <newsgroups@rvelthuis.de> |
|---|---|
| Date | 2017-04-21 09:47 +0000 |
| Message-ID | <xn0kozrhf1qqam004@nntp.aioe.org> |
| In reply to | #57659 |
Paul Rubin wrote: > "Rudy Velthuis" <newsgroups@rvelthuis.de> writes: > > Then I don't quite understand it. If you already have a mathematical > > real, then what is the problem? > > You want to find a rational approximation to your mathematical real. > E.g. suppose your real is pi. Oh, Ok, now I get it. -- Rudy Velthuis http://www.rvelthuis.de "Asswhole = a complete ass" -- John McTaggart in bpot
[toc] | [prev] | [next] | [standalone]
| From | lehs <skydda.barnen@gmail.com> |
|---|---|
| Date | 2017-04-20 20:49 -0700 |
| Message-ID | <c8c0a952-dd9b-46c6-a256-a132c213164e@googlegroups.com> |
| In reply to | #57646 |
Den torsdag 20 april 2017 kl. 19:08:51 UTC+2 skrev Rudy Velthuis:
> Paul Rubin wrote:
>
> > "Rudy Velthuis" <newsgroups@rvelthuis.de> writes:
> > > Since a real is a (finite) floating point number,
> >
> > By a "real" I meant a mathematical real like 1/pi, not a computer
> > floating point number.
>
> Then I don't quite understand it. If you already have a mathematical
> real, then what is the problem?
>
> >
> > > Or, if you want to use continued fractions, how many levels deep do
> > > you go before you quit, etc.?
> >
> > When you decide that the approximation is close enough, or that the
> > fraction has gotten too ugly.
>
> That is probably one of the possible "norm"s lehs refers to.
>
> --
> Rudy Velthuis http://www.rvelthuis.de
>
I agree. It feels wrong to consider a hypothetical measure as an exact number and too limited to find an exact reduced ratio of that number. Either the algorithm have to suggest a suite of rationals for manual selection or there should be further conditions for the algorithm in order to letting it try to find a unique ratio pair.
The measure 1.234 (without explicit error estimation) could be considered as an intervall [1.2335,1.2345). And in most cases lower a,b with a/b in the intervall are more interesting than higher a,b. In this case it's possible to make an algorithm that calculate the lowest pair (a,b) in the intervall. But of cource, if that ratio a/b is very close to a limit of the intervall one might consider more centered ratios, even if those have higher a,b.
In the case when only some numbers are allowed for a and b, the algorithm must be able to filter the search.
s" c:/ans-forth-lib/numbertheory.4th" included
\ https://github.com/Lehs/ANS-Forth-libraries
fvariable dev
: reduce-ratio \ a b -- a' b'
2dup ugcd tuck / -rot / ;
: finter \ f f' f" -- flag f<f"<f'
ftuck f> f< and ;
: fmean \ f1 f2 -- f3
f+ 2e f/ ;
\ f'>f>1, f<a/b<f'
: fratio \ f f' m n -- f" a b
false locals| flag n m |
-1 m
do i n
do fover fover j s>f i s>f f/ finter \ f f'
if fover fover fmean \ f f' fm
j s>f i s>f f/ fover f- fabs fdup dev f! \ f f' fm f1
fswap m s>f n s>f f/ f- fabs f< \ f f' f1<f2
if j to m
i to n
true to flag leave
then
then
loop flag if leave then
loop fdrop fdrop
n m reduce-ratio dev f@ ;
Given a float interval (f,f') and two integers m>n FRATIO gives the first integers a>b such that f<a/b<f' and such that f"=|fm-a/b|<|fm-m/n|, where fm is the mean of f and f'.
Here a/b>1. If x<1 examine 1/x and it's interval of accuracy:
1/r^2=a/b, in the example with the Wigner 3-j symbols.
This can be used to find a solution with wanted accuracy and divisibility.
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-04-19 15:36 -0400 |
| Message-ID | <od8e2g$430$1@dont-email.me> |
| In reply to | #57547 |
On 4/18/2017 9:48 AM, lehs wrote: > Den tisdag 18 april 2017 kl. 13:49:31 UTC+2 skrev krishna...@ccreweb.org: >> Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! >> >> https://rosettacode.org/wiki/Convert_decimal_number_to_rational >> >> However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). >> >> This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents >> >> r = -sqrt(2/(3^3*7)). >> >> When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. >> >> Incidentally, here is Forth code to compute Wigner 3j symbols -- it is somewhat limited in the range of usable angular momentum quantum numbers, though. >> >> ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg.4th >> >> and accompanying test code, >> >> ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg-test.4th >> >> Krishna > > To find an algorithm, shouldn't there be a "norm" of some kind? What is to prefer: small a and b or small difference or what? Simplest form. Here is my solution. : Rational ( F: f1 -- ) ( -- n1 n2 ) FDROP 1 1 ; It may not have the best accuracy, but it is hard to beat for simplest form. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | krishna.myneni@ccreweb.org |
|---|---|
| Date | 2017-04-20 18:44 -0700 |
| Message-ID | <9766aa75-96ec-4e95-b914-22b4a53a85b5@googlegroups.com> |
| In reply to | #57604 |
On Wednesday, April 19, 2017 at 2:36:45 PM UTC-5, rickman wrote: ... > > Simplest form. Here is my solution. > > : Rational ( F: f1 -- ) ( -- n1 n2 ) FDROP 1 1 ; > > It may not have the best accuracy, but it is hard to beat for simplest > form. > ... That approximation and throw in an RC clock oscillator -- well, you get what you pay for ;-) Krishna
[toc] | [prev] | [next] | [standalone]
| From | hughaguilar96@gmail.com |
|---|---|
| Date | 2017-04-18 07:06 -0700 |
| Message-ID | <daeeeafd-106e-492d-b7dc-5d44192da42f@googlegroups.com> |
| In reply to | #57543 |
On Tuesday, April 18, 2017 at 4:49:31 AM UTC-7, krishna...@ccreweb.org wrote: > Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! > > https://rosettacode.org/wiki/Convert_decimal_number_to_rational > > However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). > > This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents > > r = -sqrt(2/(3^3*7)). > > When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. > > Incidentally, here is Forth code to compute Wigner 3j symbols -- it is somewhat limited in the range of usable angular momentum quantum numbers, though. > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg.4th > > and accompanying test code, > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg-test.4th > > Krishna I have rational numbers in the novice-package. This goes way back to 2010. They don't work very well because the numerator and denominator are 32-bit, which is pretty small. They'll work a lot better in Straight Forth that requires a 64-bit cell and provides a double-stack that is separate from the single-stack. I don't know what you mean by a "brute force search." I wrote code that determines the GCD --- isn't that the way that it is always done?
[toc] | [prev] | [next] | [standalone]
| From | krishna.myneni@ccreweb.org |
|---|---|
| Date | 2017-04-18 19:17 -0700 |
| Message-ID | <e5142668-00d8-44f1-9508-b46a41c73545@googlegroups.com> |
| In reply to | #57548 |
On Tuesday, April 18, 2017 at 9:06:39 AM UTC-5, hughag...@gmail.com wrote: > On Tuesday, April 18, 2017 at 4:49:31 AM UTC-7, krishna...@ccreweb.org wrote: > > Rosetta Code has a number of entries for code to converting a (computer representation) of a real number into a rational number, or to the nearest expressible fraction, a/b, where both a and b are integers. There is even a Forth entry! > > > > https://rosettacode.org/wiki/Convert_decimal_number_to_rational > > > > However, it seems like many of the algorithms expressed there are brute force searches, and don't make use of the fundamental theorem of arithmetic to find the suitable integers a and b (though the code which uses library functions may do so). > > > > This particular problem has been in the back of my mind for some time, and it is one that comes up from time to time. For example, in the quantum physics of angular momentum, the Wigner 3-j symbols are real numbers between zero and one, expressible as +/-sqrt(a/b), and if one computes the quantities as real numbers, it would be nice to find (a/b) in an efficient manner. In tables of these symbols, the rational number a/b is expressed as a series of powers of prime numbers and a sign term, e.g. -1 [1 -3 0 -1] represents > > > > r = -sqrt(2/(3^3*7)). > > > > When the finite representation of the real value is given, say to double precision, a smart algorithm to find a and b, or the prime powers representation would be handy. The real to rational code is certainly useful, but I think the algorithms should be able to take advantage of the fact that |r| <= 1. It's an interesting inversion problem. > > > > Incidentally, here is Forth code to compute Wigner 3j symbols -- it is somewhat limited in the range of usable angular momentum quantum numbers, though. > > > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg.4th > > > > and accompanying test code, > > > > ftp://ccreweb.org/software/kforth/examples/fsl/extras/cg-test.4th > > > > Krishna > > I have rational numbers in the novice-package. This goes way back to 2010. > > They don't work very well because the numerator and denominator are 32-bit, which is pretty small. They'll work a lot better in Straight Forth that requires a 64-bit cell and provides a double-stack that is separate from the single-stack. > > I don't know what you mean by a "brute force search." I wrote code that determines the GCD --- isn't that the way that it is always done? Take, for example, the following real number: r = 7.61904761904762e-02 Find the fraction a/b, so that it agrees to 15 significant digits. It is a simple fraction. Can a double length GCD can do this in a reasonable time? Krishna
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2017-04-18 19:45 -0700 |
| Message-ID | <87a87df73g.fsf@nightsong.com> |
| In reply to | #57566 |
krishna.myneni@ccreweb.org writes: > r = 7.61904761904762e-02 > Find the fraction a/b, so that it agrees to 15 significant digits. Wait, that number is 8/105. That was obvious on looking at 1/r.
[toc] | [prev] | [next] | [standalone]
Page 1 of 4 [1] 2 3 4 Next page →
Back to top | Article view | comp.lang.forth
csiph-web