Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1170 > unrolled thread

Compressing data using Goldbach's conjecture?

Back to article view | Back to comp.compression

Contents

  Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 01:17 -0700
    Re: Compressing data using Goldbach's conjecture? Robert Wessel <robertwessel2@yahoo.com> - 2012-03-18 04:56 -0500
      Re: Compressing data using Goldbach's conjecture? James Dow Allen <jdallen2000@yahoo.com> - 2012-03-18 07:09 -0700
    Re: Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 03:19 -0700
      Re: Compressing data using Goldbach's conjecture? James Dow Allen <jdallen2000@yahoo.com> - 2012-03-18 06:59 -0700
        Re: Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 07:38 -0700
          Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:14 -0400
        Re: Compressing data using Goldbach's conjecture? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-18 19:30 +0000
      Re: Compressing data using Goldbach's conjecture? Ernst <Ernst_Berg@sbcglobal.net> - 2012-04-06 20:16 -0700
    Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:03 -0400
      Re: Compressing data using Goldbach's conjecture? Willem <willem@toad.stack.nl> - 2012-03-19 16:25 +0000
        Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 23:15 -0400
          Re: Compressing data using Goldbach's conjecture? michael.pohoreski@gmail.com - 2012-09-28 13:20 -0700
            Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 07:02 -0400
        Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 23:36 -0400
          Re: Compressing data using Goldbach's conjecture? Michael Pohoreski <michael.pohoreski@gmail.com> - 2012-09-29 02:19 -0700
            Re: Compressing data using Goldbach's conjecture? Thomas Richter <thor@math.tu-berlin.de> - 2012-09-29 23:43 +0200
              Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 08:47 -0400
                Re: Compressing data using Goldbach's conjecture? Thomas Richter <thor@math.tu-berlin.de> - 2012-09-30 18:25 +0200
            Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 07:14 -0400
        Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-21 00:34 -0400
        Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-22 11:46 -0400
    Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:27 -0400

Page 1 of 2  [1] 2  Next page →

#1170 — Compressing data using Goldbach's conjecture?

Suppose that Bob wants to send a message of data to Alice through a
computer network, the message can be represented as a number. Both Bob
and Alice have a list of prime numbers in a table and for each such a
number they know an index in the table.

According to Goldbach's conjecture, any even number can be represented
as a sum of two primes.

http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

Then the message m can be encoded in this way:

m = p + q + f

where p, q are primes and f is a flag which is 1 if m is odd,
otherwise it is 0

So it would work like this:

find such p and q that p + q = m - f
and their position in the table of primes

send their positions through the network

The aim is actually not to compress all data, but knowing that Bob and
Alice have both a set of same data find an usefuk information that can
be send with less cost.

[toc] | [next] | [standalone]

#1171

On Sun, 18 Mar 2012 01:17:11 -0700 (PDT), Waseihou Watashi
<waseihou@gmail.com> wrote:

>Suppose that Bob wants to send a message of data to Alice through a
>computer network, the message can be represented as a number. Both Bob
>and Alice have a list of prime numbers in a table and for each such a
>number they know an index in the table.
>
>According to Goldbach's conjecture, any even number can be represented
>as a sum of two primes.
>
>http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>
>Then the message m can be encoded in this way:
>
>m = p + q + f
>
>where p, q are primes and f is a flag which is 1 if m is odd,
>otherwise it is 0
>
>So it would work like this:
>
>find such p and q that p + q = m - f
>and their position in the table of primes
>
>send their positions through the network


As usual, the number of bits this sort of scheme generates is larger
than the inputs.  Let's say you were compressing 16 bit blocks.  There
are 6541 odd primes below 65536 (as 2 doesn't apply to this
situation).  You scheme will require sending two indexes (~12.7 bits
each) plus your "odd" flag, for a ballpark of 26.3 bits for each 16
bit input block.  A bit of cleverness in encoding ought to shave a
couple of bits off that, but you're still well into negative
territory.


>The aim is actually not to compress all data, but knowing that Bob and
>Alice have both a set of same data find an usefuk information that can
>be send with less cost.


That's called the model.  Every useful (lossless) compression
technique has a model it applies to the input stream.  To the extent
that the input stream matches the expected model, you get compression.
But when it doesn't match, you get an expansion.  In some cases fixed
dictionaries can be effectively used.  Unfortunately, the better the
model is at compressing data it matches, the less possible inputs will
match.

[toc] | [prev] | [next] | [standalone]

#1175

On Mar 18, 4:56 pm, Robert Wessel <robertwess...@yahoo.com> wrote:
> As usual, the number of bits this sort of scheme generates is larger
> than the inputs....
> You scheme will require sending two indexes (~12.7 bits each)...

One of the primes can *often* be very small so you can send it
second and use a coding suitable for usually-small numbers,
e.g. a variation of Elias-gamma.

But there is another reason why some expansion is inevitable
in this scheme.  When there are multiple solutions to n = p+q,
the (p,q) you transmit will not only provide the information n,
but also provide the information of *which* of the several
possible (p,q) you chose to send.  This information may have no
value to the receiver but nevertheless will translate to
wasted space in the compressed file.

Many compression schemes have such wastage.  I wonder if anyone
knows of methods in real-world use that recover useful info
from such redundant wastage.  The amount of such info easily
recovered may be small, but could still be exploited, e.g. as
digital signatures or secret channels.

James Dow Allen

[toc] | [prev] | [next] | [standalone]

#1172

On Sunday, March 18, 2012 9:17:11 AM UTC+1, Waseihou Watashi wrote:
> Suppose that Bob wants to send a message of data to Alice through a
> computer network, the message can be represented as a number. Both Bob
> and Alice have a list of prime numbers in a table and for each such a
> number they know an index in the table.
> 
> According to Goldbach's conjecture, any even number can be represented
> as a sum of two primes.
> 
> http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
> 
> Then the message m can be encoded in this way:
> 
> m = p + q + f
> 
> where p, q are primes and f is a flag which is 1 if m is odd,
> otherwise it is 0
> 
> So it would work like this:
> 
> find such p and q that p + q = m - f
> and their position in the table of primes
> 
> send their positions through the network
> 
> The aim is actually not to compress all data, but knowing that Bob and
> Alice have both a set of same data find an usefuk information that can
> be send with less cost.

Would it be possible to find p,q,s such that:

M = P1^2 + S1
S1 = P2^2 + S2
S2 = P3^2 + S3
...
Si = Pi+1^2 + Si+1
...
Sn is a prime number
Pi is a prime number

and the algorithm would be fast enough?

Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.

[toc] | [prev] | [next] | [standalone]

#1174

On Mar 18, 3:17 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> The aim is actually not to compress all data, but knowing that Bob and
> Alice have both a set of same data find an usefuk information that can
> be send with less cost.

Unclear.

On Mar 18, 5:19 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.

The digits of pi are often suggested as a "well known" sequence.
But I'm still unclear.  Are you suggesting something like the
following?

"To read Dan Brown's latest book for free, start at the
6,744,310,499,540,213'th bit of pi and run the next million
bits through 'unzip'."

Is yours a question about the law?  :-}

James

[toc] | [prev] | [next] | [standalone]

#1176

On Sunday, March 18, 2012 2:59:46 PM UTC+1, James Dow Allen wrote:
> On Mar 18, 3:17 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> > The aim is actually not to compress all data, but knowing that Bob and
> > Alice have both a set of same data find an usefuk information that can
> > be send with less cost.
> 
> Unclear.
> 
> On Mar 18, 5:19 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> > Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.
> 
> The digits of pi are often suggested as a "well known" sequence.
> But I'm still unclear.  Are you suggesting something like the
> following?
> 
> "To read Dan Brown's latest book for free, start at the
> 6,744,310,499,540,213'th bit of pi and run the next million
> bits through 'unzip'."
> 
> Is yours a question about the law?  :-}
> 
> James

No, it is not about law, that is only my reason because I personally believe that there should exist absolut frdeeom of eprXesiSon and that could be accomplished only if it is not possible to find out who is the originator of a message.

Whatever, from now I will focus only on asking question related to the compression part. I know that the approach with Pi could be also possible in theory, but it seems to me better to go with prime numbers and integer arithmetics.

What is needed is that Alice and Bob share a large resource like several millions of prime numbers, and Alice want to send a compressed message to Bob which can be used to reconstruct the data. The amount of data actually needed to reconstruct the message might be several times bigger than the original message, the trick should be that compressed message would be small. We can use computing power of both Alice and Bob, they have computers and time.

For example:

1. Alice want to send message M to Bob, M is a big even integer.
2. She finds out two primes P,Q so that M = P + Q, P <= Q.
3. She make a compressed message that contains information on how to find P, Q: The information can be for examle hash(P), hash(Q). hash(X) := X mod BIG_PRIME.
The message also contains SHA-256(M) checksum, maybe some other could be used.
4. Bob will receive the message and search his hash table in an attempt to find all possible pairs of Pi Qj which he will use to reconstruct candidate soulution Mc = Pi + Qj and found all Mc's where SHA-256(Mc) = SHA-256(M). Hopefully he will found only one which is the file. So Bob does not get the full information but only a range where he should search and how to decide if the result is correct.

The trick is that SHA-256 produces output with constant size no matter how input is big and the probability of collision is VERY LOW. Of course several hashes could be chained for better verification. It is still theoretically possible that collision would happen and junk would be obtained, but that's ok as long as the probability is negligible.

Only hashes could be sent through network and because they are small, it is much easier to send them through networks like i2p, tor or hidden with steganography into some image. Those methods all provides a reasonable amount of amNonyMtmity for poster.

The problem is searching the space which has O(n^2) and of course founding the primes.

[toc] | [prev] | [next] | [standalone]

#1180

"Waseihou Watashi" <waseihou@gmail.com> wrote in message 
news:18762373.298.1332081533211.JavaMail.geo-discussion-forums@ynca15...
> On Sunday, March 18, 2012 2:59:46 PM UTC+1, James Dow Allen wrote:
>> On Mar 18, 3:17 pm, Waseihou Watashi <wasei...@gmail.com> wrote:

    [clipped]

> The message also contains SHA-256(M) checksum, maybe some other could be 
> used.
> 4. Bob will receive the message and search his hash table in an attempt to 
> find all possible pairs of Pi Qj which he will use to reconstruct 
> candidate soulution Mc = Pi + Qj and found all Mc's where SHA-256(Mc) = 
> SHA-256(M). Hopefully he will found only one which is the file. So Bob 
> does not get the full information but only a range where he should search 
> and how to decide if the result is correct.
>
> The trick is that SHA-256 produces output with constant size no matter how 
> input is big and the probability of collision is VERY LOW. Of course 
> several hashes could be chained for better verification. It is still 
> theoretically possible that collision would happen and junk would be 
> obtained, but that's ok as long as the probability is negligible.
>
> Only hashes could be sent through network and because they are small, it 
> is much easier to send them through networks like i2p, tor or hidden with 
> steganography into some image. Those methods all provides a reasonable 
> amount of amNonyMtmity for poster.
>
> The problem is searching the space which has O(n^2) and of course founding 
> the primes.

    So why not have a bit more cleverness and reformat your data blocks?

1110100000001011101110011

Becomes a 5x5 grid
11101
00000
00101
11011
10011
Take the SHA-256 of that value

Rotate your grid 90 degrees
11001
01001
00101
11000
11101

1100101001001011100011101
Take the SHA-256 of that value

Since the data is identical in rotation, the SHA-256 hash collision will be 
very distinct between the two data sets.

    You won't compress this data this way, but whom am I to stop a fool and 
their hobbies? 

[toc] | [prev] | [next] | [standalone]

#1177

James Dow Allen <jdallen2000@yahoo.com> wrote:

(snip)
> The digits of pi are often suggested as a "well known" sequence.
> But I'm still unclear.  Are you suggesting something like the
> following?

> "To read Dan Brown's latest book for free, start at the
> 6,744,310,499,540,213'th bit of pi and run the next million
> bits through 'unzip'."

I thought it had to be in base 11.

-- glen

[toc] | [prev] | [next] | [standalone]

#1209

On Sunday, March 18, 2012 3:19:22 AM UTC-7, Waseihou Watashi wrote:
> On Sunday, March 18, 2012 9:17:11 AM UTC+1, Waseihou Watashi wrote:
> > Suppose that Bob wants to send a message of data to Alice through a
> > computer network, the message can be represented as a number. Both Bob
> > and Alice have a list of prime numbers in a table and for each such a
> > number they know an index in the table.
> > 
> > According to Goldbach's conjecture, any even number can be represented
> > as a sum of two primes.
> > 
> > http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
> > 
> > Then the message m can be encoded in this way:
> > 
> > m = p + q + f
> > 
> > where p, q are primes and f is a flag which is 1 if m is odd,
> > otherwise it is 0
> > 
> > So it would work like this:
> > 
> > find such p and q that p + q = m - f
> > and their position in the table of primes
> > 
> > send their positions through the network
> > 
> > The aim is actually not to compress all data, but knowing that Bob and
> > Alice have both a set of same data find an usefuk information that can
> > be send with less cost.
> 
> Would it be possible to find p,q,s such that:
> 
> M = P1^2 + S1
> S1 = P2^2 + S2
> S2 = P3^2 + S3
> ...
> Si = Pi+1^2 + Si+1
> ...
> Sn is a prime number
> Pi is a prime number
> 
> and the algorithm would be fast enough?
> 
> Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.
Um, If there is a dataset such that one can simply index that to obtain some data it woudl require the size of the data plus at least one bit


On Sunday, March 18, 2012 3:19:22 AM UTC-7, Waseihou Watashi wrote:
> On Sunday, March 18, 2012 9:17:11 AM UTC+1, Waseihou Watashi wrote:
> > Suppose that Bob wants to send a message of data to Alice through a
> > computer network, the message can be represented as a number. Both Bob
> > and Alice have a list of prime numbers in a table and for each such a
> > number they know an index in the table.
> > 
> > According to Goldbach's conjecture, any even number can be represented
> > as a sum of two primes.
> > 
> > http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
> > 
> > Then the message m can be encoded in this way:
> > 
> > m = p + q + f
> > 
> > where p, q are primes and f is a flag which is 1 if m is odd,
> > otherwise it is 0
> > 
> > So it would work like this:
> > 
> > find such p and q that p + q = m - f
> > and their position in the table of primes
> > 
> > send their positions through the network
> > 
> > The aim is actually not to compress all data, but knowing that Bob and
> > Alice have both a set of same data find an usefuk information that can
> > be send with less cost.
> 
> Would it be possible to find p,q,s such that:
> 
> M = P1^2 + S1
> S1 = P2^2 + S2
> S2 = P3^2 + S3
> ...
> Si = Pi+1^2 + Si+1
> ...
> Sn is a prime number
> Pi is a prime number
> 
> and the algorithm would be fast enough?
> 
> Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.

Um, this is a simple conversation with no qualifiers and no proof.  I do not want to fight. I have nothing to defend.

 As far as I can tell it is possible to do something similar to what you suggest.
 I think you are describing an Indirect Transfer Protocol.  Such that Alice gets a data and from that she constructs the message. But the actual message isn't the data she gets.

 I just asked if anyone on BitTorrent was interested in an Indirect Transfer Protocol.  

 No one was interested so I am moving on to other projects.


You have to admit that if we can download the instructions to construct a file and not traffic in the actual data there are legal aspects.  Perhaps more for China and such than the USA.  I admit I'd like to see more freedom for many of this world.

 Anyway.. This is a strictly opinion-based reply; I do see it.  I do know how I would construct such a thing. 

 Good luck!  I think I get your drift.

[toc] | [prev] | [next] | [standalone]

#1179

"Waseihou Watashi" <waseihou@gmail.com> wrote in message 
news:6f3960da-3058-41fc-8770-0db735674034@z31g2000vbt.googlegroups.com...
> Suppose that Bob wants to send a message of data to Alice through a
> computer network, the message can be represented as a number. Both Bob
> and Alice have a list of prime numbers in a table and for each such a
> number they know an index in the table.
>
> According to Goldbach's conjecture, any even number can be represented
> as a sum of two primes.

    Whew, there are ONLY EVEN NUMBERS in this universe?  I was worried for a 
moment there.

> http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>
> Then the message m can be encoded in this way:
>
> m = p + q + f

    M = (binary digit 0 or 1) + prime number + (escape character) + another 
prime number
    I'm assuming that you're using the "most compact method of storing 
primes" (all primes except 2 & 5, in Base 10 end in 1 or 3 or 7 or 9, 
therein, storing the end result + a multiple of 10 is the most compact 
unit).
00 = 1
01 = 3
10 = 7
11 = 9
5-digit prime number:
(Base 10) 11027 = (Binary) 10101100010011 (14 binary digits)
(Base 10) 1102 (*10 which you can drop) + 7 =
(Binary) 10001001110 (11 binary digits + append) 10 (binary substitution of 
7) = 1000100111010 (13 binary digits)

http://benvitale-funwithnum3ers.blogspot.com/2011/02/5-digit-prime-numbers.html

    Of course this method only REALLY saves space when you're going full 
grid positional notation.
(Each binary '1' equals a prime, binary '0' equals a non-prime)
1110 (01,03,07,09) = 10*0 + prime end digit
1111 (11,13,17,19) = 10*1 + prime end digit
0101 (21,23,27,29) = 10*2 + prime end digit
1010 (31,33,37,39) = 10*3 + prime end digit
    (1st line = 1, 11, 111 = 6 binary digits + 3 escape characters becomes 4 
binary digits)
    (2nd line = 1011, 1101, 10001, 10011 = 18 binary digits + escapes into 4 
binary digits)
    (3rd line = 10111, 11101 = 10 binary digits + escapes into 4 binary 
digits)
    (4th line = 11111, 100111 = 11 binary digits + escapes into 4 binary 
digits)
    Thusly 45 binary digits + 7 escape characters becomes 16 binary digits.
    (Figured this out 3 decades ago, even when I was having "learning 
difficulties", what were YOU doing then?)

> where p, q are primes and f is a flag which is 1 if m is odd,
> otherwise it is 0
>
> So it would work like this:
>
> find such p and q that p + q = m - f
> and their position in the table of primes
>
> send their positions through the network
>
> The aim is actually not to compress all data, but knowing that Bob and
> Alice have both a set of same data find an useful information that can
> be send with less cost.

    Prime number (base 10) 12907 + (base 10) 16993 = 29900
    Prime number (base 02) 11.0010.0110.1011 + 100001001100001 = 
111010011001100
12907 = 11001001101011 (14 binary digits)
16993 = 100001001100001 (15 binary digits)
29900 = 111010011001100 (15 binary digits)
    You'd require 29 binary digits + 1 appended binary digit to represent 
(even or odd) = 30 binary digits
    To then represent a number of 15 binary digit length?

(And we assume your target number is 29900 or 29911)
Making the binary digit string into: 1110100110011000 or 1110100110011001

    Using the generic "Table of Primes":
http://primes.utm.edu/nthprime/  (Nth Prime)
prime(1536) = 12907 + prime(1960) =16993
(base 10) 1536 = (base 02) 11000000000 (11 binary digits)
(base 10) 1960 = (base 02) 11110101000 (11 binary digits)
    Thusly you'd require at minimum 22 binary digits + 1 appended binary 
digit = 23 binary digits to represent a number of 15 binary digit length.

    Even converting using my most compact method is rather more efficient 
than yours.
    "Keep fucking that chicken" kid, you'd provided me with my daily 
mathematical laugh.
    You weren't too big on the whole concept of HOMEWORK in school, were 
you? 

[toc] | [prev] | [next] | [standalone]

#1182

George Johnson wrote:
) "Waseihou Watashi" <waseihou@gmail.com> wrote in message 
) news:6f3960da-3058-41fc-8770-0db735674034@z31g2000vbt.googlegroups.com...
)> Suppose that Bob wants to send a message of data to Alice through a
)> computer network, the message can be represented as a number. Both Bob
)> and Alice have a list of prime numbers in a table and for each such a
)> number they know an index in the table.
)>
)> According to Goldbach's conjecture, any even number can be represented
)> as a sum of two primes.
)
)     Whew, there are ONLY EVEN NUMBERS in this universe?  I was worried for a 
) moment there.
)
)> http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
)>
)> Then the message m can be encoded in this way:
)>
)> m = p + q + f
)
)     M = (binary digit 0 or 1) + prime number + (escape character) + another 
) prime number
)     I'm assuming that you're using the "most compact method of storing 
) primes" (all primes except 2 & 5, in Base 10 end in 1 or 3 or 7 or 9, 
) therein, storing the end result + a multiple of 10 is the most compact 
) unit).

No, the most compact method of storing primes is to store the ordinal
number in the sequence of primes.  IOW: for the Nth prime, you store
the number N.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#1183

"Willem" <willem@toad.stack.nl> wrote in message 
news:slrnjmenhi.1pqk.willem@toad.stack.nl...
> George Johnson wrote:
> ) "Waseihou Watashi" <waseihou@gmail.com> wrote in message
> ) 
> news:6f3960da-3058-41fc-8770-0db735674034@z31g2000vbt.googlegroups.com...
> )> Suppose that Bob wants to send a message of data to Alice through a
> )> computer network, the message can be represented as a number. Both Bob
> )> and Alice have a list of prime numbers in a table and for each such a
> )> number they know an index in the table.
> )>
> )> According to Goldbach's conjecture, any even number can be represented
> )> as a sum of two primes.
> )
> )     Whew, there are ONLY EVEN NUMBERS in this universe?  I was worried 
> for a
> ) moment there.
> )
> )> http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
> )>
> )> Then the message m can be encoded in this way:
> )>
> )> m = p + q + f
> )
> )     M = (binary digit 0 or 1) + prime number + (escape character) + 
> another
> ) prime number
> )     I'm assuming that you're using the "most compact method of storing
> ) primes" (all primes except 2 & 5, in Base 10 end in 1 or 3 or 7 or 9,
> ) therein, storing the end result + a multiple of 10 is the most compact
> ) unit).
>
> No, the most compact method of storing primes is to store the ordinal
> number in the sequence of primes.  IOW: for the Nth prime, you store
> the number N.
>
>
> SaSW, Willem
> -- 
> Disclaimer: I am in no way responsible for any of the statements
>            made in the above text. For all I know I might be
>            drugged or something..
>            No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

    Okay.  Let's try that for a list.
Prime(1) = 1 (Binary 1)
Prime(2) = 2 (Binary 10)
Prime(3) = 3 (Binary 11)
Prime(4) = 5 (Binary 101)
Prime(5) = 7 (Binary 111)
Prime(6) = 11 (Binary 1011)
Prime(7) = 13 (Binary 1101)

    Well, let's see, so far you're using WAY more binary digits than I am 
(plus Escape Characters)
.
    I admit that I am "Cheating" a tad by not including 2 & 5 as Primes in 
the list as a matter of function per speed of grid list access, but I don't 
see you winning the long race in Compact Prime Number List Storage.

    Of course this method only REALLY saves space when you're going full 
grid positional notation.
(Each binary '1' equals a prime, binary '0' equals a non-prime)

1110 (01,03,07,09) = 10*0 + prime end digit
1111 (11,13,17,19) = 10*1 + prime end digit
0101 (21,23,27,29) = 10*2 + prime end digit
1010 (31,33,37,39) = 10*3 + prime end digit

    (1st line = 1, 11, 111 = 6 binary digits + 3 escape characters becomes 4 
binary digits)
    (2nd line = 1011, 1101, 10001, 10011 = 18 binary digits + escapes into 4 
binary digits)
    (3rd line = 10111, 11101 = 10 binary digits + escapes into 4 binary 
digits)
    (4th line = 11111, 100111 = 11 binary digits + escapes into 4 binary 
digits)
    Thusly 45 binary digits + 7 escape characters becomes 16 binary digits.
    (Figured this out 3 decades ago, even when I was having "learning
difficulties", what were YOU doing then?)

    ==============

    Oooh, I know, how about RELATIVE difference Prime storage?
1 = 1 (Binary 1)
2 = 2-1 = 1 (Binary 1)
3 = 3-2 = 1 (Binary 1)
5 = 5-3 = 2 (Binary 10)
7 = 7-5 = 2 (Binary 10)
11 = 11-7 = 4 (Binary 100)
13 = 13-11 = 2 (Binary 10)
17 = 17-13 = 4 (Binary 100)
19 = 19-17 = 2 (Binary 10)

    Very compact.
    I liked this method a long time ago (despite it lacking quick random 
access).
    Itty Bitty Problem.  You have to store Escape Characters (they cost you) 
too.
    Ah, but let's be generous.
    Primes 1 to 19 (Binary Difference Storage) = 1,1,10,10,100,10,100,10
    16 Binary Digits (plus Escape Characters) versus my 12 Binary Digits so 
far.
    But let me be generous again and allow you to skip 2 & 5 as I do.
    The Primes 1 to 19 (Binary Difference Storage) now is = 
1,10,100,100,10,100,10
    Which eats up 16 Binary Digits again (plus Escape Characters).
    So let me be generous yet again.

    After Prime Number 3, there are no more differences of 1 and all are 
multiples of 2.
    So you are free to drop one trailing zero after all Prime Difference 
Storage locations.
     The Primes 1 to 19 (Binary Difference Storage) now is = 
1,1,10,10,1,10,1
    Which is a much more compact list of 10 Binary Digits (plus Escape 
characters).

    Oh, but don't let me stop you.
    I believe the Escape Characters are doing that job pretty damned well 
already.

 

[toc] | [prev] | [next] | [standalone]

#1532

On Monday, March 19, 2012 8:15:04 PM UTC-7, George Johnson wrote:
> "Willem" wrote in message 
> Prime(1) = 1 (Binary 1)
> Prime(2) = 2 (Binary 10)
> Prime(3) = 3 (Binary 11)
> Prime(4) = 5 (Binary 101)
> Prime(5) = 7 (Binary 111)
> Prime(6) = 11 (Binary 1011)
> Prime(7) = 13 (Binary 1101)
>     Well, let's see, so far you're using WAY more binary digits than I am 
> (plus Escape Characters)
>     I admit that I am "Cheating" a tad by not including 2 & 5 as Primes in 
> the list as a matter of function per speed of grid list access, but I don't 
> see you winning the long race in Compact Prime Number List Storage.
>     Of course this method only REALLY saves space when you're going full 
> grid positional notation.
> (Each binary '1' equals a prime, binary '0' equals a non-prime)
> 1110 (01,03,07,09) = 10*0 + prime end digit
> 1111 (11,13,17,19) = 10*1 + prime end digit
> 0101 (21,23,27,29) = 10*2 + prime end digit
> 1010 (31,33,37,39) = 10*3 + prime end digit
>     (1st line = 1, 11, 111 = 6 binary digits + 3 escape characters becomes 4 
> binary digits)
>     (2nd line = 1011, 1101, 10001, 10011 = 18 binary digits + escapes into 4 
> binary digits)
>     (3rd line = 10111, 11101 = 10 binary digits + escapes into 4 binary 
> digits)
>     (4th line = 11111, 100111 = 11 binary digits + escapes into 4 binary 
> digits)
>     Thusly 45 binary digits + 7 escape characters becomes 16 binary digits.
>     (Figured this out 3 decades ago, even when I was having "learning
> difficulties", what were YOU doing then?)

Aside from the bug where you have 1 marked as prime, you've just described a compact version of the Fundamental Prime Constant that tells if any number is prime:

Sum( i = 1, inf, if IsPrime(i) then 2^-i else 0  ) 
= 0.41468250985111166024810962215430770836577423813791697786824541448864096...

See:
http://oeis.org/A051006
web.axelero.hu/fadorjan/aronsf.pdf

i.e.
   i = decimal place after the decimal point.
so....

0.0110101...
........^ 7 is prime, so the 7th bit after the decimal point is set
......^ 5 is prime, so the 5th bit after the decimal point is set
....^ 3 is prime, so the 3rd bit after the decimal point is set
...^ 2 is prime, so the 2nd bit after the decimal point is set
..^ 1 is not prime, so the 1st bit after the decimal is NOT set

In practice you multiply the constant by 4 and subtract 1 (to remove storing '1', '2') and you would also remove every other zero since the constant is also storing the fact that every even number is redundantly stored as a 0 in every other bit (that is, every even bit position.)

Removing all the even numbers ...

With 45 bits we can test numbers up to 91
0.111011011010011001011010010011001011001010010
.......^ 13 yes
......^ 11 yes
.....^ 9 no
....^ 7 yes
...^ 5 yes
..^ 3 yes

This sequence has the form:
  n = bit_position*2 + 3 

IsPrime_TableOdd( n )
  bit_position = (n - 3) / 2;
  n_is_prime = bits[ bit_position ]

i.e. IsPrime_TableOff( 13 )
 bit_position = (13-3)/2 = 5, bits[5] = true; thus 13 is prime


However, this still not a very optimal storage scheme since we are *still* storing redundant zeroes.
We can do better since *every* prime > 5 is ALWAYS of the form:  6n+/-1

Thus with 44 bits we can test numbers up to 6*(46/2) = 134 which is a ~50% increase in search space!
0.111111101101111010110111011010011111100001101100
.........^ 25 no
........^ 23 yes
.......^ 19 yes
......^ 17 yes
.....^13 yes
....^11 yes
...^7 yes
..^ 5 yes

i.e.
 5, 7: 11
11,13: 11
17,19: 11
23,25: 10
29,31: 11
35,37: 01
41,43: 11
47,49: 10
53,55: 10
59,61: 11
65,67: 01
71,73: 11
77,79: 01
83,85: 10
89,91: 10
95,97: 01
101,103: 11
107,109: 11
113,115: 10
119,121: 00
125,127: 01
131,133: 10

IsPrime_Table6n( n )
  if (n < 7) return true if n is 2, 3, 5, else false
  if n is even return false

  add1 = (n+1) mod 6
  sub1 = (n-1) mod 6
  if (add1 is zero) or (sub1 is zero)
     bit_position = floor( n/3 ) - 1
  else
     return false

  n_is_prime = bits[ bit_position ];

Fast, and compact. ;-)

Michael

[toc] | [prev] | [next] | [standalone]

#1535

<michael.pohoreski@gmail.com> wrote in message 
news:23cb3815-f50a-4898-9190-ed08e5c04501@googlegroups.com...
> On Monday, March 19, 2012 8:15:04 PM UTC-7, George Johnson wrote:
>> "Willem" wrote in message
>> Prime(1) = 1 (Binary 1)
>> Prime(2) = 2 (Binary 10)
>> Prime(3) = 3 (Binary 11)
>> Prime(4) = 5 (Binary 101)
>> Prime(5) = 7 (Binary 111)
>> Prime(6) = 11 (Binary 1011)
>> Prime(7) = 13 (Binary 1101)
>>     Well, let's see, so far you're using WAY more binary digits than I am
>> (plus Escape Characters)
>>     I admit that I am "Cheating" a tad by not including 2 & 5 as Primes 
>> in
>> the list as a matter of function per speed of grid list access, but I 
>> don't
>> see you winning the long race in Compact Prime Number List Storage.
>>     Of course this method only REALLY saves space when you're going full
>> grid positional notation.
>> (Each binary '1' equals a prime, binary '0' equals a non-prime)
>> 1110 (01,03,07,09) = 10*0 + prime end digit
>> 1111 (11,13,17,19) = 10*1 + prime end digit
>> 0101 (21,23,27,29) = 10*2 + prime end digit
>> 1010 (31,33,37,39) = 10*3 + prime end digit
>>     (1st line = 1, 11, 111 = 6 binary digits + 3 escape characters 
>> becomes 4
>> binary digits)
>>     (2nd line = 1011, 1101, 10001, 10011 = 18 binary digits + escapes 
>> into 4
>> binary digits)
>>     (3rd line = 10111, 11101 = 10 binary digits + escapes into 4 binary
>> digits)
>>     (4th line = 11111, 100111 = 11 binary digits + escapes into 4 binary
>> digits)
>>     Thusly 45 binary digits + 7 escape characters becomes 16 binary 
>> digits.
>>     (Figured this out 3 decades ago, even when I was having "learning
>> difficulties", what were YOU doing then?)
>
> Aside from the bug where you have 1 marked as prime, you've just described 
> a compact version of the Fundamental Prime Constant that tells if any 
> number is prime:
>
> Sum( i = 1, inf, if IsPrime(i) then 2^-i else 0  )
> = 
> 0.41468250985111166024810962215430770836577423813791697786824541448864096...
>
> See:
> http://oeis.org/A051006
> web.axelero.hu/fadorjan/aronsf.pdf
>
> i.e.
>   i = decimal place after the decimal point.
> so....
>
> 0.0110101...
> ........^ 7 is prime, so the 7th bit after the decimal point is set
> ......^ 5 is prime, so the 5th bit after the decimal point is set
> ....^ 3 is prime, so the 3rd bit after the decimal point is set
> ...^ 2 is prime, so the 2nd bit after the decimal point is set
> ..^ 1 is not prime, so the 1st bit after the decimal is NOT set
>
> In practice you multiply the constant by 4 and subtract 1 (to remove 
> storing '1', '2') and you would also remove every other zero since the 
> constant is also storing the fact that every even number is redundantly 
> stored as a 0 in every other bit (that is, every even bit position.)
>
> Removing all the even numbers ...
>
> With 45 bits we can test numbers up to 91
> 0.111011011010011001011010010011001011001010010
> .......^ 13 yes
> ......^ 11 yes
> .....^ 9 no
> ....^ 7 yes
> ...^ 5 yes
> ..^ 3 yes
>
> This sequence has the form:
>  n = bit_position*2 + 3
>
> IsPrime_TableOdd( n )
>  bit_position = (n - 3) / 2;
>  n_is_prime = bits[ bit_position ]
>
> i.e. IsPrime_TableOff( 13 )
> bit_position = (13-3)/2 = 5, bits[5] = true; thus 13 is prime
>
>
> However, this still not a very optimal storage scheme since we are *still* 
> storing redundant zeroes.
> We can do better since *every* prime > 5 is ALWAYS of the form:  6n+/-1
>
> Thus with 44 bits we can test numbers up to 6*(46/2) = 134 which is a ~50% 
> increase in search space!
> 0.111111101101111010110111011010011111100001101100
> .........^ 25 no
> ........^ 23 yes
> .......^ 19 yes
> ......^ 17 yes
> .....^13 yes
> ....^11 yes
> ...^7 yes
> ..^ 5 yes
>
> i.e.
> 5, 7: 11
> 11,13: 11
> 17,19: 11
> 23,25: 10
> 29,31: 11
> 35,37: 01
> 41,43: 11
> 47,49: 10
> 53,55: 10
> 59,61: 11
> 65,67: 01
> 71,73: 11
> 77,79: 01
> 83,85: 10
> 89,91: 10
> 95,97: 01
> 101,103: 11
> 107,109: 11
> 113,115: 10
> 119,121: 00
> 125,127: 01
> 131,133: 10
>
> IsPrime_Table6n( n )
>  if (n < 7) return true if n is 2, 3, 5, else false
>  if n is even return false
>
>  add1 = (n+1) mod 6
>  sub1 = (n-1) mod 6
>  if (add1 is zero) or (sub1 is zero)
>     bit_position = floor( n/3 ) - 1
>  else
>     return false
>
>  n_is_prime = bits[ bit_position ];
>
> Fast, and compact. ;-)
>
> Michael

    It is still much less efficient in space storage versus using 4 bits to 
store a chunk of 4 potential primes per ever 10 increment. The binary 
difference storage method saves some space at the outset, but wastes space 
every time from the jump of 3 to 7.

    Easily proven with the below routine.

N*10 + {ending in 1,3,7,9} (binary digit 0 = not prime; binary digit 
1=prime)

    {1,3,7,9} gaps:
11-9=2
3-1=2
7-3=4
9-7=2

    Let's say you have a set of 100% primes, then your gap list (divided by 
2 after it reaches 5) will always have a gap at the 3 to 7 jump.
    Hypothetical all primes string in binary: 1101111011110111101111011...
    As each prime that ends in 3 jumps to a prime ending in 7, then it has 
an extra 01 jump.
 

[toc] | [prev] | [next] | [standalone]

#1184

"Willem" <willem@toad.stack.nl> wrote in message 
news:slrnjmenhi.1pqk.willem@toad.stack.nl...
> George Johnson wrote:
> ) "Waseihou Watashi" <waseihou@gmail.com> wrote in message
> ) 
> news:6f3960da-3058-41fc-8770-0db735674034@z31g2000vbt.googlegroups.com...
> )> Suppose that Bob wants to send a message of data to Alice through a
> )> computer network, the message can be represented as a number. Both Bob
> )> and Alice have a list of prime numbers in a table and for each such a
> )> number they know an index in the table.
> )>
> )> According to Goldbach's conjecture, any even number can be represented
> )> as a sum of two primes.
> )
> )     Whew, there are ONLY EVEN NUMBERS in this universe?  I was worried 
> for a
> ) moment there.
> )
> )> http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
> )>
> )> Then the message m can be encoded in this way:
> )>
> )> m = p + q + f
> )
> )     M = (binary digit 0 or 1) + prime number + (escape character) + 
> another
> ) prime number
> )     I'm assuming that you're using the "most compact method of storing
> ) primes" (all primes except 2 & 5, in Base 10 end in 1 or 3 or 7 or 9,
> ) therein, storing the end result + a multiple of 10 is the most compact
> ) unit).
>
> No, the most compact method of storing primes is to store the ordinal
> number in the sequence of primes.  IOW: for the Nth prime, you store
> the number N.
>
>
> SaSW, Willem
> -- 
> Disclaimer: I am in no way responsible for any of the statements
>            made in the above text. For all I know I might be
>            drugged or something..
>            No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

For the primes up to 3559 I will require
355 * 4 = 1420 Binary Digits of memory.
Prime(499) = 3559
499 = Binary 1 1111 0011 compared to 3559 = Binary 110111100111
7 bits versus  12 bits, a saving of 4 bits.
 What you gain in space savings you lose in computational time.

    You also need a list of the Nth Primes stored in some compact form (or 
you will be required to recompute this list at a later time).
 

[toc] | [prev] | [next] | [standalone]

#1533

On Monday, March 19, 2012 8:36:50 PM UTC-7, George Johnson wrote:
> "Willem" wrote in message 
> For the primes up to 3559 I will require
> 355 * 4 = 1420 Binary Digits of memory.

You only need 1186 bits if you store the pairs 6n-1 and 6n+1, where n > 0, in the array.  Use the bit position as in index into the array.

i.e.
0.111111101101111010110111011010011111100001101100 ...
.........^ 25 no
........^ 23 yes
.......^ 19 yes
......^ 17 yes
.....^13 yes
....^11 yes
...^7 yes
..^ 5 yes 

See my post below for details on how to convert n to bit_position.

[toc] | [prev] | [next] | [standalone]

#1534

On 29.09.2012 11:19, Michael Pohoreski wrote:
> On Monday, March 19, 2012 8:36:50 PM UTC-7, George Johnson wrote:
>> "Willem" wrote in message
>> For the primes up to 3559 I will require
>> 355 * 4 = 1420 Binary Digits of memory.
>
> You only need 1186 bits if you store the pairs 6n-1 and 6n+1, where n>  0, in the array.  Use the bit position as in index into the array.

Actually, you need zero bits to store it. If you want to retrieve the 
n'th prime, just compute it.

IOW, I'm not quite sure what you're trying to say. Yes, of course you 
can compress the sequence of the primes by a suitable algorithm and 
represent it more compactly. Such a suitable algorithm is the classical 
sieve, for example, and the most compact representation of it is zero bits.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1537

"Thomas Richter" <thor@math.tu-berlin.de> wrote in message 
news:k47q26$h8a$1@news2.informatik.uni-stuttgart.de...
> On 29.09.2012 11:19, Michael Pohoreski wrote:
>> On Monday, March 19, 2012 8:36:50 PM UTC-7, George Johnson wrote:
>>> "Willem" wrote in message
>>> For the primes up to 3559 I will require
>>> 355 * 4 = 1420 Binary Digits of memory.
>>
>> You only need 1186 bits if you store the pairs 6n-1 and 6n+1, where n> 
>> 0, in the array.  Use the bit position as in index into the array.
>
> Actually, you need zero bits to store it. If you want to retrieve the n'th 
> prime, just compute it.
>
> IOW, I'm not quite sure what you're trying to say. Yes, of course you can 
> compress the sequence of the primes by a suitable algorithm and represent 
> it more compactly. Such a suitable algorithm is the classical sieve, for 
> example, and the most compact representation of it is zero bits.
>
> Greetings,
> Thomas

    So how do you know which "Nth Prime" it is if you don't have a reference 
list?
    Tell me what is the 4875th "Nth Prime" without using a list or a list 
lookup tool like Mathworld or another website like it. There is no such 
thing as a Nth Prime unless you have a stored list somewhere, which requires 
hard drive space or an Internet connection to remotely download it (which 
takes computation time & bandwidth off that website).

    Or, you have to sieve out all of the prior prime numbers, instantly 
discard them, then arrive at your answer. Which wastes computational time 
unless you store a list on your hard drive.

    The next easiest way would be to use a precomputed statistical 
approximation graph of the primes per a location on the number line (but 
will not be as accurate as a precomputed list).

The Nth Prime Algorithm
A prime page by Andrew Booker
http://primes.utm.edu/nthprime/algorithm.php
In order to find a prime quickly, the nth prime program uses a large stored 
data table to get close to the right answer first, then finishes with a 
relatively short computation.  To see how this works, imagine the number 
line broken into bins, each of size N, i.e. the first is from 0 to N-1, the 
second from N to 2N-1, etc. 

[toc] | [prev] | [next] | [standalone]

#1538

On 30.09.2012 14:47, George Johnson wrote:
> "Thomas Richter"<thor@math.tu-berlin.de>  wrote in message
> news:k47q26$h8a$1@news2.informatik.uni-stuttgart.de...
>> On 29.09.2012 11:19, Michael Pohoreski wrote:
>>> On Monday, March 19, 2012 8:36:50 PM UTC-7, George Johnson wrote:
>>>> "Willem" wrote in message
>>>> For the primes up to 3559 I will require
>>>> 355 * 4 = 1420 Binary Digits of memory.
>>>
>>> You only need 1186 bits if you store the pairs 6n-1 and 6n+1, where n>
>>> 0, in the array.  Use the bit position as in index into the array.
>>
>> Actually, you need zero bits to store it. If you want to retrieve the n'th
>> prime, just compute it.
>>
>> IOW, I'm not quite sure what you're trying to say. Yes, of course you can
>> compress the sequence of the primes by a suitable algorithm and represent
>> it more compactly. Such a suitable algorithm is the classical sieve, for
>> example, and the most compact representation of it is zero bits.
>>
>> Greetings,
>> Thomas
>
>      So how do you know which "Nth Prime" it is if you don't have a reference
> list?

By writing a "decompressor" from a zero bit input, of course. And the 
decompressor is the sieve algorithm. There was no complexity limitation 
stated in the problem, so why does it have to be an O(N) algorithm to 
"decompress" N digits?

>      Tell me what is the 4875th "Nth Prime" without using a list or a list
> lookup tool like Mathworld or another website like it.

Why "without"? Why do I have it "without it"? Decompession also works 
*with* an algorithm, so does it here.

> There is no such
> thing as a Nth Prime unless you have a stored list somewhere, which requires
> hard drive space or an Internet connection to remotely download it (which
> takes computation time&  bandwidth off that website).

Sorry for my simple-minded platonism, but I'm fairly sure that there is 
a n-th prime even without having computed it. I'm also certain that 
there are infinitely many, thus there is certainly a 4875th prime.

>      Or, you have to sieve out all of the prior prime numbers, instantly
> discard them, then arrive at your answer. Which wastes computational time
> unless you store a list on your hard drive.

And your point is? Decompression is always a "waste of computational 
power". You could have stored the uncompressed original in first place!

[toc] | [prev] | [next] | [standalone]

#1536

"Michael Pohoreski" <michael.pohoreski@gmail.com> wrote in message 
news:4ae00e74-68b4-4a49-968d-9f1a64c0fbdc@googlegroups.com...
> On Monday, March 19, 2012 8:36:50 PM UTC-7, George Johnson wrote:
>> "Willem" wrote in message
>> For the primes up to 3559 I will require
>> 355 * 4 = 1420 Binary Digits of memory.
>
> You only need 1186 bits if you store the pairs 6n-1 and 6n+1, where n > 0, 
> in the array.  Use the bit position as in index into the array.
>
> i.e.
> 0.111111101101111010110111011010011111100001101100 ...
> .........^ 25 no
> ........^ 23 yes
> .......^ 19 yes
> ......^ 17 yes
> .....^13 yes
> ....^11 yes
> ...^7 yes
> ..^ 5 yes
>
> See my post below for details on how to convert n to bit_position.

    Anyway, I'm a tad bored on this.
    SO LET US GET NON-BORING!

    One of the problems of data transmission is ERROR CORRECTION.
    Well, with most error-correction methods, you have to burn an extra 2 
bits per 4 bits in play.

    So what if we could bypass that ENTIRELY and use 0% extra space for CRC 
coding?
    How, you may ask?
    Well, by using a pre-generated 100% compact bitstream as a XOR reference 
mask.
    Use any non-repeating sequence in binary (square root of 2 or PI or 
non-integer number conversion stream or my compact prime number list or any 
long pseudo-random stream).

    Using the XOR reference mask, a stream of 0 bits would be the exact 
equal to the non-repeating generator set upon reception. Any variance in the 
bit-stream would indicate a variance from the non-repeating XOR'd output. 
The costs are found in computational time in the sender & receiver's 
computers.  Since PI has a math trick to get the HEXadecimal digits of PI at 
any location, the costs of even that are minimal.

Bellard's formula
http://en.wikipedia.org/wiki/Bellard%27s_formula

Bailey-Borwein-Plouffe formula
http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula

Spigot algorithm
http://en.wikipedia.org/wiki/Spigot_algorithm
A spigot algorithm is a type of algorithm used to compute the value of a 
mathematical constant such as ? or e. Spigot algorithms are unique because 
they do not require the total number of digits to be fixed beforehand, and 
do not require the computation of several intermediate results which are 
combined to produce the final result.[1] There are two kinds of spigot 
algorithms: (1) those that can produce a single, arbitrary digit (also 
called digit extraction algorithm); and (2) those that produce a sequence of 
digits, one after the other. The Bailey-Borwein-Plouffe formula is a digit 
extraction algorithm for ? which produces hexadecimal digits. A sequential 
spigot algorithm for ? was produced by Stanley Rabinowitz and Stanley Wagon 
(this algorithm is sometimes referred to as "the spigot algorithm for 
?").[2] Spigot algorithms that produce a sequence of digits begin producing 
digits and produce them continuously, rather than waiting for the entire 
algorithm to finish. Spigot algorithms are known for ? and e. Spigot 
algorithms typically work in a particular radix, such as hexadecimal or 
binary number.
 

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compression

csiph-web