Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think there is a way of doing radix conversion in a stream-oriented fashion in lexicographic order. However, what I've come up with isn't sufficient for actually doing it, and it has a couple of assumptions:</p> <ol> <li>The length of the positional numbers are already known.</li> <li>The numbers described are integers. I've not considered what happens with the maths and -ive indices. </li> </ol> <p>We have a sequence of values <em>a</em> of length <em>p</em>, where each value is in the range [0,<em>m</em>-1]. We want a sequence of values <em>b</em> of length <em>q</em> in the range [0,<em>n</em>-1]. We can work out the <em>k</em>th digit of our output sequence <em>b</em> from <em>a</em> as follows:</p> <p>b<sub>k</sub> = floor[ sum(a<sub>i</sub> * m<sup>i</sup> for i in 0 to p-1) / n<sup>k</sup> ] mod n</p> <p>Lets rearrange that sum into two parts, splitting it at an arbitrary point <em>z</em></p> <p>b<sub>k</sub> = floor[ ( sum(a<sub>i</sub> * m<sup>i</sup> for i in z to p-1) + sum(a<sub>i</sub> * m<sup>i</sup> for i in 0 to z-1) ) / n<sup>k</sup> ] mod n</p> <p>Suppose that we don't yet know the values of a between [0,z-1] and can't compute the second sum term. We're left with having to deal with ranges. But that still gives us information about <em>b<sub>k</sub></em>.</p> <p>The minimum value <em>b<sub>k</sub></em> can be is:</p> <p>b<sub>k</sub> >= floor[ sum(a<sub>i</sub> * m<sup>i</sup> for i in z to p-1) / n<sup>k</sup> ] mod n</p> <p>and the maximum value <em>b<sub>k</sub></em> can be is:</p> <p>b<sub>k</sub> &lt;= floor[ ( sum(a<sub>i</sub> * m<sup>i</sup> for i in z to p-1) + m<sup>z</sup> - 1 ) / n<sup>k</sup> ] mod n</p> <p>We should be able to do a process like this:</p> <ol> <li>Initialise <em>z</em> to be <em>p</em>. We will count down from <em>p</em> as we receive each character of <em>a</em>.</li> <li>Initialise <em>k</em> to the index of the most significant value in <em>b</em>. If my brain is still working, ceil[ log<sub>n</sub>(m<sup>p</sup>) ].</li> <li>Read a value of <em>a</em>. Decrement <em>z</em>.</li> <li>Compute the min and max value for <em>b<sub>k</sub></em>.</li> <li>If the min and max are the same, output <em>b<sub>k</sub></em>, and decrement k. Goto 4. (It may be possible that we already have enough values for several consecutive values of <em>b<sub>k</sub></em>)</li> <li>If <em>z</em>!=0 then we expect more values of <em>a</em>. Goto 3.</li> <li>Hopefully, at this point we're done.</li> </ol> <p>I've not considered how to efficiently compute the range values as yet, but I'm reasonably confident that computing the sum from the incoming characters of <em>a</em> can be done much more reasonably than storing all of <em>a</em>. Without doing the maths though, I won't make any hard claims about it though!</p>
    singulars
    1. This table or related slice is empty.
    1. PONumber base conversion as a stream operation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USWuggy
    1. USWuggy
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI don't think you can throw away the second term in the sum, because floor(a+b) ≠ floor(a) + floor(b) in general. If the first term is just a tiny fraction less than an integer, the value of the second term is very significant.
      singulars
      1. PO
      1. USAdam Rosenfield
    2. COI think I've (erroneously) stated the conditions for selecting z. Conceptually what I'm trying to do is to use a range for the incoming number 'a'. As we get each digit, the range that 'a' can be narrows. Once it is narrow enough, we can know with certainty (in any base we like) what the initial sequence is (i.e. if we're converting 0x4b?? to decimal, even missing the last 2 digits we know that the first decimal digits are 19, since the number can only be between 19200 and 19455. I'll re-examine what I've done and see if I can express it correctly in an edit.
      singulars
      1. PO
      1. USWuggy
    3. COThis process reminds me of arithmetic decompress (range decoding?) - which might be enough to show that any stream can be split into digits uniquely. I think there is a pathalogical case where you can't output the next digit until you've seen all the incoming stream.
      singulars
      1. PO
      1. UScaffiend
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload