Date: Jan 4, 2013 9:47 PM
Author: David Bernier
Subject: Re: Another count sort that certainly must exist, it do not have<br> any restrictions upon size of (S number of possibilities)
On 01/04/2013 08:29 PM, JT wrote:
> On 4 Jan, 18:07, David Bernier<david...@videotron.ca> wrote:
>> On 01/04/2013 10:46 AM, JT wrote:
>>> On 4 Jan, 15:46, JT<jonas.thornv...@gmail.com> wrote:
>>>> I remember doing this in a tentamen during my education in information
>>>> theory beleiving what i did was binary sort but my teacher informed me
>>>> it wasn't so what is it.
>>>> By creating a Pascal pointer binary tree with each leaf holding a
>>>> integer, you move the binary numbers to the tree from least digit to
>>>> highest using left legs for 0's and right for 1's. (Basicly creating
>>>> leaves for new numbers, and at last digit you add 1 to the leaf slot.
>>>> So after you moved all values into the tree and created all the nodes,
>>>> you simply read out all the none zero values holded into the slot of
>>>> the leaves within the binary tree.
>>>> What is this sort called?
>>>> Of course you cannot have more leaves then memory, but this does not
>>>> need to hold memory for slots never used like the array slots, it is
>>>> therefore my beleif that this sort could be useful also for database
>>>> purposes sorting basicly anything. What do you think?
>>> I can see there would be problems reading out the sizes of a binary
>>> tree from smallest to biggest, if you have legs with different
>>> lengths? Is there any algorithmic solution to this problem.
>>> I have kind of a foul play solution, you create a binary tree for
>>> every digit bigger then 2^20 the smaller ones you run with the array
>>> approach. So for 21,22,23... bits and so on each numbers run on their
>>> own computers, with 2048 computers you could sort enormous amount of
>>> data of different size. So basicly the "heaps?" all have legs with
>>> same sizes and is easy to read out in order.
>>> Is this a working idea or just plain silly, maybe it is just easier to
>>> use one computer and read out the values from the heap and sort them
>>> with quicksort after you filled up the tree? (Is it called tree or
>>> heap, what is the difference betwee a heap and a tree?).
>>> So what you think about the mix using this kind of sort for counting
>>> in values, and then quicksort to sort the none null tree nodes by
>> Oops.. below is about factoring. The best algorithms
>> have been getting better since Maurice Kraitchik's [1920s]
>> improvement on Fermat's method of expressing a number
>> as a difference of squares, n = a^2 - b^2, so
>> n = (a-b) (a+b).
>> There's a very good article called "A Tale of Two Sieves"
>> by Carl Pomerance: Notices of the AMS, vol. 43, no. 12,
>> December 1996:
>> The 9th Fermat number F_9 = 2^(512)+1 had been factored
>> around 1990 by the Lenstras et al using the Number Field
>> sieve (which had supplanted the quadratic sieve).
>> The Quadratic sieve is easier to understand than the
>> Number Field Sieve, which I don't understand.
>> F_10 and F_11 were fully factored then, using the elliptic
>> curve method (which can find smallish prime factors).
>> F_12 was listed as not completely factored, with
>> F_12 being a product of 5 distinct odd primes and
>> the 1187-digit composite:
>> C_1187 =
>> At 3942 bits for C_1187 above, what's the
>> probability density function of expected time
>> till C_1187 is fully factored?
>> Or, centiles: e.g. 50% chance fully factored
>> within<= 10 years. 95% chance fully factored within
>> <= 95 years, etc. ...
> Is this idea the same sort as the other counting sort, it seem more
> adjustable to sort anysized number when just fitting them into the
> binary tree.
I gave a reply that should have been in reply to your question about
the complexity of factoring integers.
The most important ideas for the quadratic sieve [for factoring]
are not related to sorting algorithms.
Sorting algorithms are well analyzed in Knuth's tomes. I forgot
the title of the series of two to three tomes.