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