Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)

Replies: 11   Last Post: Jan 8, 2013 1:37 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
JT

Posts: 1,148
Registered: 4/7/12
Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)

Posted: Jan 4, 2013 8:29 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
> > sizes.

>
> 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:
> <http://www.ams.org/notices/199612/index.html>
>
> 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 =
> 22964766349327374158394934836882729742175302138572\
> 22257593176439130841895160961323826592803808643123\
> 15776330453915314460450194556572637889591520959595\
> 00781101126096495656976145338084323609391242570049\
> 59146146100932078255130896682422242552873156911153\
> 49491277441664272360127694182069497019299146312879\
> 53679124328078403443589001544785043209243005176672\
> 36512498567556601129618233580642646148465607080211\
> 50483896593552361820682419503442019994498256473415\
> 56766313684295383743697537161298411893329950259437\
> 02457251084955979786901113201153080673107947314499\
> 89885761657097352227077484815352368256239445951125\
> 33741234160090993221997405711848497115626313770615\
> 84634017936609811822404415794282448107580150138831\
> 67949250345497227202182371779894151535731419443909\
> 33701532957472310726727304029461192020120667119324\
> 40906462375814643855500503626564314311613740004222\
> 88239457400101057642788560965414596506825478363862\
> 10032027169896230115182649724551245475912070548418\
> 45921140740300676916471986974995922243980616471547\
> 01759458614628952014532145179607626863555620392963\
> 07129357252744645128034273466002900209575716007479\
> 66912966168394403107609922082657201649660373439896\
> 3042158832323677881589363722322001921.
>
> 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. ...
>
> dave


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.


Date Subject Author
1/4/13
Read Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/8/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
kiru.sengal@gmail.com
1/8/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.