Wikipedia:Reference desk/Archives/Mathematics/2011 October 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 25

Randomly ordering a set of non-duplicating integers?

Is there a way to generate integers (in a range) in a random order, skipping none, duplicating none, in a psudo-random, deterministic way?

Perhaps a Minimal perfect hash function for integers?

I would like to randomly seek a hard disk, but I want to make sure to seek to every sector exactly once. Ariel. (talk) 09:31, 25 October 2011 (UTC)

If I understand the question correctly, it can be done with the following pseudocode:

function permute (array a)
{
 n = a.length;
 b = new array (n);
 for i = 1 to n
 {
  j = 1+floor((n-i+1)*rnd);
  b[i] = a[j];
  a[j] = a[n];
 }
 return b;
}

-- Meni Rosenfeld (talk) 10:29, 25 October 2011 (UTC)

I quite forgot to write that I can't store the array. It would be huge, in the 10s of GB. I need to generate the random integers algorithmically. Ariel. (talk) 10:58, 25 October 2011 (UTC)

You could just use a Linear congruential generator for a bigger number (not too much bigger!) and remove entries which are too large. If you want a bit of extra randomness over that get a bunch of say 100 at a time and randomize them using the above algorithm. Dmcq (talk) 11:29, 25 October 2011 (UTC)

A linear congruential generator probably isn't good because you would need to output all bits of the state to avoid duplicates, but the low bits are not very random. You could use a LFSR instead. A better (though slower) approach would be to encrypt the numbers 0, 1, 2, ... sequentially with a block cipher primitive, all using the same key (which acts as the seed). The Hasty Pudding Cipher supports a block size of any integral number of bits. It hasn't been analyzed much and may not be cryptographically secure, but it should at least produce numbers that pass all ordinary statistical tests. RSA would also work, but it's pretty slow. -- BenRG (talk) 18:31, 26 October 2011 (UTC)

The LFSR worked, but this is a pretty interesting idea. Can it really encrypt each 32 bit block (number) to a distinct other 32 bit block? Ariel. (talk) 02:01, 27 October 2011 (UTC)

That was why I was suggesting they randomize blocks from it. An LFSR is no better at avoiding patterns. The problem with a better randomizing algorithm is that you get duplicates. Dmcq (talk) 21:12, 26 October 2011 (UTC)

An LFSR worked nicely, thank you. (I had trouble finding parameters for the LCG that guaranteed a full period.) I don't need it that random, I'm just testing that the hard disk can seek correctly, and that it can read/write every block correctly (that's why I need full period). Ariel. (talk) 01:47, 27 October 2011 (UTC)

You don't need an exact period, that's what I was saying about the linear congruential generator. If you do a number a bit higher then you can just discard the numbers which are too high. BenRG misunderstood this point. If the cycle is N and your max is n then you simply repeat for numbers between and N and you do N/n tries on average - which is why you don't want N too much larger. I'd have thought for a hard disk you'd want to test the near seeks a bit more thoroughly than far away ones and it would speed up the testing quite a bit to cut down on the far seeks. It souns to me like this testing is going to take quite a long time! Dmcq (talk) 11:12, 27 October 2011 (UTC)

Yes, exactly. I am just ignoring numbers that are too high. Hmm, I wonder if there is a way to strongly randomize the low bits, but change the high bits less often, but still have a full period. I could easily just do the drive in sections, but it seems less "pure". And yes, the test is taking a long time, it may be too much of a test :) And LGC doesn't randomize the low bits much right? If I invert the number, that might work (although I still don't know what parameters to use for each bit size, I need 26 bits to 36 bits). Ariel. (talk) 20:20, 27 October 2011 (UTC)

10 GB? Here's an idea. Suppose you choose a fast and cryptographically secure random hash function. Let this map the set of your numbers {0, …, N-1} to a small set {0, …, k-1} such that an array of size N/k easily fits into your memory. You'll do k passes: in pass l, you iterate through all numbers and find those whose hash key is l, collecting all these to an array. You shuffle this array and use it as the next approx N/k values of your permutation. If, like you say, you have only like 10**10 numbers, then k won't be very large. The drawback is that in theory the run time of this is quadratic in N; and that you can't access the permutation randomly, but if I understand you right, you don't need that. – b_jonas 19:36, 26 October 2011 (UTC)

Does this really guarantee that every number will be generated once and only once? Ariel. (talk) 01:47, 27 October 2011 (UTC)

If you need only a little bit random, and don't care if it is really random, then a simple approach is to choose a random permutation and apply it is to the bits of your index. Then you simply step through the possible indices, permuting the bits of each in turn via the same permutation function, and you arrive at a new index. This will allow you to jump around a lot, and the pattern of jumps will be different each time, but it certainly won't be truly random. Depending on the application that may be good enough. Dragons flight (talk) 21:40, 26 October 2011 (UTC)

The index would be too big, around 10GB I estimated. I also need to make sure not to get the same number twice (since I write random data to the sector, if I write it twice then during the read pass it will look like an error since the second write won't match the first read). Ariel. (talk) 01:47, 27 October 2011 (UTC)

Read my suggestion again, it doesn't require you to maintain a complete index and it avoids repetitions. Dragons flight (talk) 02:22, 27 October 2011 (UTC)

By "index" I simply mean a single integer that says which sector (or whatever) you are looking at during the current iteration. Dragons flight (talk) 02:24, 27 October 2011 (UTC)

Ah, got it. But that random permutation function is exactly what I was asking - what function should I use. (I was answered earlier in this thread.) Ariel. (talk) 04:24, 27 October 2011 (UTC)

Dragons flight's suggestion was to use a permutation on the bits in the binary representation of an integer. If you have 10^11 sectors then that's 37 bits, so you only need a permutation on the integers 0-36. So you have i run from 0 to 10^11, and let j be i's bits permuted accordingly. -- Meni Rosenfeld (talk) 13:20, 27 October 2011 (UTC)

There is something I am not getting here. I understand I need to permute the bits - but with what pattern? The pattern was the question, I know I need to permute the bits. Ariel. (talk) 20:20, 27 October 2011 (UTC)

You could use the following permutation:

$1\to 6\ \ 2\to 3\ \ 3\to 19\ \ 4\to 8\ \ 5\to 27\ \ 6\to 37\ \ 7\to 25\ \ 8\to 14\ \ 9\to 24\ \ 10\to 34$

$\ \ 11\to 30\ \ 12\to 23\ \ 13\to 33\ \ 14\to 5\ \ 15\to 22\ \ 16\to 10\ \ 17\to 32\ \ 18\to 2\ \ 19\to 16$

$\ \ 20\to 17\ \ 21\to 13\ \ 22\to 9\ \ 23\to 7\ \ 24\to 36\ \ 25\to 20\ \ 26\to 12\ \ 27\to 1\ \ 28\to 15$

$\ \ 29\to 28\ \ 30\to 35\ \ 31\to 31\ \ 32\to 21\ \ 33\to 11\ \ 34\to 29\ \ 35\to 26\ \ 36\to 18\ \ 37\to 4$

This is just a random permutation I generated for 37 integers, which is easy. Then you have

${\begin{array}{c|c|c|c}i&i{\textrm {(binary)}}&j{\textrm {(binary)}}&j\\\hline 1&0000000000000000000000000000000000001&0000000000000000000000000000000100000&32\\2&0000000000000000000000000000000000010&0000000000000000000000000000000000100&4\\3&0000000000000000000000000000000000011&0000000000000000000000000000000100100&36\\\vdots &&&\end{array}}$

The randomness of this is not perfect. You probably want to make sure to map low-order bits to high-order bits to improve it.

Edit: Maybe it's best to just reverse the bits. Then you have

${\begin{array}{c|c|c|c}i&i{\textrm {(binary)}}&j{\textrm {(binary)}}&j\\\hline 1&0000000000000000000000000000000000001&1000000000000000000000000000000000000&68719476736\\2&0000000000000000000000000000000000010&0100000000000000000000000000000000000&34359738368\\3&0000000000000000000000000000000000011&1100000000000000000000000000000000000&103079215104\\\vdots &&&\end{array}}$

-- Meni Rosenfeld (talk) 12:11, 28 October 2011 (UTC)

Zero times infinity = 1? 1 divided by zero = infinity?

Just for curiosity's sake, I would like to know if this statement can possibly be mathematically correct: "Vatican City . . . is infinitely larger than its non-existent second largest settlement." Is 1 really infinitely larger than 0, or was that mere hyperbole? You can find the context over on the Miscellaneous ref desk. Since I'm a non-mathematician, please use English in your replies, at least for the first few words. Textorus (talk) 14:27, 25 October 2011 (UTC)

0*∞ is not defined. Similarly, 1/∞ is not defined. In Calculus, there are definitions of functions in which a value approaches infinity. For example, f(x)=0*x. As x approaches infinity, f(x) approaches zero (well, it sits at zero the whole time). If f(x)=1/x, then as x approaches infinity, f(x) approaches zero. -- kainaw™ 14:39, 25 October 2011 (UTC)

As our indeterminate form article points out, 0*∞ and 1/∞ are valid shorthand forms for describing limits, but that they are not at all similar as the first is indeterminate while the second is not. -- 110.49.224.157 (talk) 07:39, 31 October 2011 (UTC)

Yes, informally speaking, 1 is infinitely bigger than 0. We say that a number x is t times bigger than a number y if we have to add y together t times to get x. For example, 6 is three times bigger than 2: 2 + 2 + 2 = 6. Similarily, 12 is 1.5 times bigger than 8 because 12 = 8 + 1⁄2 × 8. Now think about 0 and 1. How many times do you need to add 0 together to get 1? Well you can add 0 together as many times as you like and you'd never get 1 as the answer: 0 = 0 + 0 = 0 + 0 + 0 = …, etc. That's why, informally speaking, 1 is infinitely bigger than 0; in a futile attempt to get to 1, you would have to add 0 together again and again, for ever and ever, i.e. "infinitely many times". — Fly by Night (talk) 15:32, 25 October 2011 (UTC)

To avoid possible ambiguities, one would say "times as big as", or "bigger by a factor of", but such precise language is commonly ignored, even by mathematicians! Dbfirs 07:05, 26 October 2011 (UTC)

1/0=∞ in the real projective line and in $[0,\infty ]$. The phrase "1 is infinitely bigger then 0" is best understood in the context of the latter. You also have 1/∞=0. However, these structures don't adhere to the usual multiplication rules - although 1/0=∞, it is not true that 0⋅∞=1. -- Meni Rosenfeld (talk) 16:27, 25 October 2011 (UTC)

Obvious comment: typical usage of the word "bigger" would be something like "5 is 2 bigger than 3", or "1 is 1 bigger than 0". So in that sense "1 is infinitely bigger than 0" is a major overstatement. Putting the word "times" in there, as in "8 is 2 times bigger than 4" changes everything, as stated above by others. Staecker (talk) 21:55, 25 October 2011 (UTC)

${\frac {1}{0}}$ is not defined. However, if x approaches 0, 1/x approaches infinity: $\lim _{x\to 0^{+}}{\frac {1}{x}}=\infty$

English explanation: lim means, when x gets closer and closer to 0 (ignore the + by it), 1/x gets closer and closer to infinity. And when it is x->infinity, it means when x becomes arbitrarily big, i.e., 'getting closer to infinity'.

Similarly, $\lim _{x\to \infty }{\frac {1}{x}}=0$
0*infinity depends on what is being used to generate it.
$\lim _{x\to \infty }0x=0\qquad \lim _{x\to 0}x{\frac {1}{x^{2}}}=\infty \qquad \lim _{x\to 0}cx{\frac {1}{x}}=c$
tl;dr For the first one, pretty much. For the second, you cannot answer. KyuubiSeal (talk) 22:42, 25 October 2011 (UTC)

Saying that 1/0 is undefined is like saying that ${\sqrt {-1}}$ is undefined. They are both defined in a suitable algebraic structure. -- Meni Rosenfeld (talk) 06:15, 26 October 2011 (UTC)

Sorry, I forgot about the extended real line. Although, would it be positive or negative infinity? I think the second point still holds though. KyuubiSeal (talk) 14:31, 26 October 2011 (UTC)

In the extended real number line 1/0 is undefined. In the real projective line $\infty =-\infty$ and $1/0=\infty$. -- Meni Rosenfeld (talk) 15:20, 26 October 2011 (UTC)

0⋅∞ = ℝ {-∞<ℝ<∞} ∴ 1/∞ = 0 ∵ 1 = ℝ {-∞<ℝ<∞} Plasmic Physics (talk) 06:37, 26 October 2011 (UTC)

Meaing zero time infinity equals any real number between negative and positive infinity therefore, one divided by infinity equals zero since one is a real number between negative and positive infinity. So, zero times infinity equals one, pi, e, etc., and one, pi, e, etc. divided by infinity equal zero. Plasmic Physics (talk) 06:46, 26 October 2011 (UTC)

Well, as I interpret the intriguing Vatican City claim, it holds water simply because it does not say that the nonexistent settlement is zero in size (and with a zero area, we wouldn't have any hot interior places to visit would we,:-), thus consider that the Vatican City should be infinitely larger than any infinitesimally smaller place of nonzero size, regardless of whether or not it exists. Now my math background is limited, but I think at least one way to arrive at this solution is the use of an extended real number line the hyperreal numbers with the set {R,∞,-∞,1/∞,-1/∞} where {1/∞,-1/∞} are infinitesimals such that 1/∞>0>-1/∞. (alternatively, one can require 1/∞=0) Then, letting the larger city area A equal 1 and the area B of the smaller settlement equal 1/∞ we have the ratio 1:1/∞ of the two areas, then A/B=1/(1/∞)=1*∞=∞, thus A=B*∞, showing that the Vatican City is infinitely larger than the other place. Modocc (talk) 07:57, 26 October 2011 (UTC)

So, you are claiming that there is the probability of a city that is smaller than the smallest subatomic particle? -- kainaw™ 14:23, 26 October 2011 (UTC)

There is a bit of a problem with dealing with the statement. It would be just as reasonable to say the second largest city in the Vatican is twenty times as large as the Vatican. Dmcq (talk) 17:55, 26 October 2011 (UTC)

The hypothetical infinitesimal settlement does not exist in accordance with the OP's statement. Furthermore, the OP clearly asked only if the statement about this nonexistent settlement could be mathematically correct, and not whether it was true. The statement A=B*∞ given is untrue should the settlement almost coincide with Vatican City such that A=B+1/∞ because the Vatican City would need to be an infinitesimal and it is not. --Modocc (talk) 18:32, 26 October 2011 (UTC)

YES ∀n ∈ N: n * settlement = n * 0 = 0 < Vatican

DS Belgium (talk) 00:42, 27 October 2011 (UTC)

Ah-nice, that works too. Above if for the B arkarea I had chosen or defined 1/∞=0 then A=0*∞ which is obviously not the best result. Keeping with the nonzero infinitesimal though gives, A*B>0 or A>0/(1/∞)=0*∞, showing also that the Vatican is larger than an infinite number of zeros. Modocc (talk) 06:24, 27 October 2011 (UTC)

Thanks guys, I knew this question would generate some lively discussion. Fly_by_night gets the award for the best answer in English. For the best answer in math, I'll let you all decide by a show of hands. Textorus (talk) 12:23, 27 October 2011 (UTC)

Idempotents in a category

Hello everyone, I'm very confused about the last part of a question and getting nowhere with it, maybe you can help.

First of all, a morphism $e:A\to A$ is called 'idempotent' if ee = e. An idempotent is said to 'split' if it can be factored as fg, where gf is an identity morphism in a category. For a class of idempotents ${\mathcal {E}}$ in a category ${\mathcal {C}}$, we define ${\mathcal {C}}[{\mathcal {E}}]$ as the category whose objects are members of ${\mathcal {E}}$ and whose morphisms $d\to e$ are the morphisms $f:domd\to dome$ in ${\mathcal {C}}$ for which efd=f, with composition the same as in ${\mathcal {C}}$: I have proved this is a valid category (in fact I believe it is the Cauchy completion of ${\mathcal {C}}$). I have also shown that if ${\mathcal {E}}$ is a class of idempotents containing all identity morphisms of ${\mathcal {C}}$, then there is a full & faithful functor $I:{\mathcal {C}}\to {\mathcal {C}}[{\mathcal {E}}]$.

Now, I want to show that an arbitrary functor $T:{\mathcal {C}}\to {\mathcal {D}}$ can be factored as $T={\bar {T}}I$ for some ${\bar {T}}$ iff it sends the members of ${\mathcal {E}}$ to split idempotents in ${\mathcal {D}}$. However, I'm completely stuck now. I don't really see what information being a 'split' idempotent adds - if we assume $T$ splits idempotents, I don't feel like I have any more information to factor $T$, though I suppose can try to factor it in the obvious way given the behavior of I, and if $T$ factors I can't see why it should split idempotents. Help hugely appreciated, many thanks in advance! Estrenostre (talk) 19:32, 25 October 2011 (UTC)

The Lorentz attractor in Lagrange notation

Can I have the equations for the Lorentz attractor in Lagrange notation and the solutions to the derivatives in the equations? Also, is the Lorentz attractor parametric? --Melab±1 ☎ 21:36, 25 October 2011 (UTC)

Do you mean the Lorenz oscillator? The Lorenz attractor is a complex fractal set of points in 3D space that doesn't directly have an equation. In any case you should probably read our article. Looie496 (talk) 00:09, 26 October 2011 (UTC)

The Lorenz attractor is depicted as being parametric in Mac OS X's Grapher. --Melab±1 ☎ 00:10, 26 October 2011 (UTC)

Well, they are confused then. Looie496 (talk) 00:13, 26 October 2011 (UTC)

That's the syntax that works. I'll try to make it in wikitext. --Melab±1 ☎ 00:40, 26 October 2011 (UTC)

Here: ${\frac {d}{dt}}\left[{\begin{array}{c}x\\y\\z\end{array}}\right]=\left[{\begin{array}{c}10\left(y-x\right)\\28x-y-xz\\-{\frac {8}{3}}z+xy\end{array}}\right],\;\left[{\begin{array}{c}x\\y\\z\end{array}}\right]=\left[{\begin{array}{c}-10\\10\\25\end{array}}\right],\;t=0\dots 30$ --Melab±1 ☎ 00:45, 26 October 2011 (UTC)

Those are the equations for the Lorenz oscillator. If you run them for unlimited time, the solution converges to the Lorenz attractor, but it would not be correct to say that the solution is the Lorenz attractor. As time goes on, you get closer and closer to each point in the attractor, but you never actually reach it. Looie496 (talk) 16:35, 26 October 2011 (UTC)

What I am trying get from them are parametric equations that can be used to plot the trajectory of the Lorenz attractor, in the form of

$x(t)=$

$y(t)=$

$z(t)=$

--Melab±1 ☎ 21:06, 26 October 2011 (UTC)

Can anyone fill the equations in in that form? --Melab±1 ☎ 20:33, 27 October 2011 (UTC)

I will be astonished if anyone can. This would be, in effect, providing an explicit solution to the Lorenz oscillator. Systems of non-linear differential equations like this seldom have explicit solutions in terms of simple functions. Also, if an explicit solution were known, them Edward Lorenz would not have needed to use numerical approximations to study the behaviour of the oscillator in the first place. Gandalf61 (talk) 07:53, 28 October 2011 (UTC)

Then how is it solved and where does "t" come into play? --Melab±1 ☎ 01:43, 29 October 2011 (UTC)