In terms of code the mod function is unnecessary (and may be costly) - just generate three random bits by the coin tossing, join them together either by shifting or maybe there is a less costly way (depends on the processor architecture). This will give a binary representation of an integer in the range 0 to 7. We only want 1 to 6 so start over when the result is 0 or 7.
Right, but what architecture has a u3 data type? I'm using the mod to reset any 1's that got shifted left of the 3 bits I'm using. I suppose I could do a bitwise-and with 7 for the same effect, if that would perform better. Or do you mean just start over at 0 for each roll regardless?
Quote:
If the coin toss is a costly process for the processor (for example if it stops and waits for a human to toss a real coin and type in the result) then you can use the two 'throw away' values to generate the first bit for the next attempted dice roll - if you're throwing away a 0 then the first bit would be 0 and if you throw away a 7 the first bit would be a 1.
For the thought experiment, we are assuming that we have an actual coin when what we really need is a die, so yeah we can assume a super slow human coin-flip. I did originally consider that if we rolled a 0 or 7, we could shift left just once and flip again, but I thought that might favor 110 and 001, since those are the only possible non-0/7 results that can follow 0/7, so essentially 6 and 1 would show up twice as often as 2 through 5.
But what if we always only shifted it by 1, and continued to keep the good rolls and toss the bad? My initial gut suspicion is that the distribution would stay even (once we shift the leading few 0s out of the pipeline), but not the "randomness" of the sequence or order or whatever, since certain numbers would necessarily only follow other certain numbers.
What about shifting by 2? That's essentially your scheme for the throw-away numbers, but would it work for all the numbers?
__________________
Last edited by Ensign Steve; 10-05-2015 at 07:52 PM.
I don't think you need the mod function even if you use an 8, 16, 32, 64 or whatever data type. Yes, you start over with either 0 or 4 regardless each time - but setting a value to a constant is usually less costly in terms of processor time than using the mod function to trim a value. Here's one way to do it, (and I chose not to use shifts either in this example - setting each of the three bits by adding 1, 2 or 4):
Code:
def roll_die():
result = 8 # special flag value to force three flips for first roll
while result == 0 or result > 6: # we need to roll the die
if result == 8: # first roll, so we need a random most significant bit (msb)
result = 4 * flip_coin() # randomly choose 0 or 1 for msb
else if result == 7: previous roll was 7 so we can set the msb
result = 4
# else the previous roll was 0, then msb is clear (no code needed)
result += 2 * flip_coin() # random middle bit
result += flip_coin() # random least significant bit
return result
The first coin flip now determines whether the eventual returned die roll will be 1,2,3 or 4,5,6
The last coin flip determines whether the die roll is odd or even.
When the result happens to be 7, then the next pass randomly chooses between 4, 5, and 6 (or 7 again).
When the result happens to be 0, then the next pass randomly chooses between 1, 2, and 3, (or 0 again).
The while loop calls flip_coin() three times for the first pass, and then if the result happens to be 0 or 7 it only calls flip_coin() twice for any subsequent passes.
You are correct that the very first flip decides between a low (1,2,3) or high (4,5,6) eventual outcome - but this doesn't introduce any bias - after all, it's a random flip so in the long run we will get equal numbers of low or high rolls.
The first flip having decided a high or low result, the remaining two flips select from the three useful outcomes, or the one 'try again' outcome with equal distribution - so again no bias can be introduced providing flip_coin() is genuinely random.
If you want to optimize the function further you can eliminate the test for the flag value from the loop by unrolling the code. You have a non-loop section that randomly generates 0 to 7 using three flips for the first try, and then while loops that only execute if/while the result is either 0 or 7. The while loops use two flips to randomly select a low result (0,1,2,3) when the previous result was 0, or a high (4,5,6,7) result when the previous result was 7.
Code:
def roll_die():
# randomly generate 0 to 7 for first attempt
result = 4 * flip_coin() + 2 * flip_coin() + flip_coin()
while result == 0: #randomly choose 1, 2, or 3 (or 0 again)
result = 2 * flip_coin() + flip_coin()
while result == 7: #randomly choose 4, 5, or 6 (or 7 again)
result = 4 + 2 * flip_coin() + flip_coin()
return result
__________________
Last edited by ceptimus; 10-06-2015 at 04:42 PM.
Reason: added 'unrolled' code example
The demos are both interactive, and they should work on most recent web browsers.
Something called "semisimple Lie algebras":
Quote:
These mathematical structures are important in physics for expressing the internal symmetries of space-time and elementary particles and the like. I wrote this package because it was hard to find anything online certain things that I was looking for. More specifically, decomposing product representations into irreducible ones and calculating branching rules: what representations of subalgebras does a representation of an algebra produce? It has applications like getting Standard-Model particle multiplets from Grand-Unified-Theory particle multiplets.
Contains code in Mathematica, Python, and C++; all three versions are feature-parallel except for Mathematica's graphics code.
Also, the Cayley-Dickson construction of complex numbers, quaternions, octonions, sedenions, etc.
The Cayley-Dickson construction is a nice bit of abstract algebra. It is defined recursively.
Start with some algebraic field like the real numbers and compose successive algebras from it as follows.
Addition: (a1,b1) + (a2,b2) = (a1+a2, b1+b2)
Scalar multiplication: c*(a,b) = (c*a, c*b)
Negation: -a = (-1)*a
Subtraction: a - b = a + (-b)
Conjugation: cjg(a in original set) = a
cjg((a,b)) = (cjg(a), -b)
Multiplication: (a1,b1) * (a2,b2) = (a1*a2 - cjg(b2)*b1, b2*a1 + b1*cjg(a2))
An algebra element a:
Is real if cjg(a) = a
Is imaginary if cjg(a) = -a
(extension of definition for complex numbers)
Every element can be decomposed into a real part and an imaginary part.
The norm is the real part of cjg(a)*a. The imaginary part of that product is always zero.
Real numbers (starting point)
Complex numbers -- they lose total ordering
Quaternions -- multiplication no longer commutative
Octonions -- multiplication no longer associative, though "alternative" (associative with at least two elements equal)
Sedenions -- multiplication no longer alternative, norm of product no longer equal to product of norms, some pairs of nonzero elements multiply to make zero, still power-associative
All the rest of these algebras are sedenion-like.
Power-associativity: when taking a power of an element, it does not matter which order one does the multiplications. The inverse is power -1.
Proof. Consider
A = P*(1) + Q*a where P and Q are scalars, (1) is 1 extended with 0's, and a is imaginary in this context: cjg(a) = -a
Find A12 = A1*A2. Then the P's and Q's are related with
P12 = P1*P2 - Q1*Q2*norm(a)
Q12 = P1*Q2 + P2*Q1
If one starts with some A = P*(1) + Q*a, then the P's and Q's for its powers can be found recursively. Thus, power-associativity.
What's an algebraic field? I'll explain here. I'll start with abstract-algebra groups.
First, consider a binary operation that is closed on some set S: S*S = some subset of S.
If the operation is associative: (a*b)*c = a*(b*c) for a,b,c in S, then (S,*) is a semigroup.
A semigroup with an identity, a*e = e*a = a, for all a, is a monoid.
A semigroup can have left and right identities (defined on one side), and also left and right zeros z: a*z = z*a = z. A monoid with a zero has only one element.
A monoid with inverse elements, a*inv(a) = inv(a)*a = e for all a, is a group.
A commutative group is often called an abelian one. Noncommutative ones are nonabelian.
All the finite abelian groups are known. They are products of cyclic groups with (power of a prime) elements. A cyclic group Z(n) contains {e, a, a^2, ..., a^(n-1)} or {0, 1, ..., n-1 with addition modulo n}.
The finite nonabelian groups are a much more difficult task, but all the "simple" ones are now known. There are several infinite families of them, and 26 "sporadic" ones, including the huge "Monster" group. The proof of this result required 10,000 journal pages.
There are also infinite groups, of course. Some of them are discrete, like the group of integers under addition, some are continuous, like the group of real numbers under addition, and some are mixed, like the group of nonzero real numbers under multiplication.
Continuous ones that can be generated as powers of elements close to the identity element are called "Lie groups". The differences between such elements and the identity is some small number times a "Lie algebra", the group's algebra. It is often much more convenient to work with a Lie group's algebra than it is to work with the group itself. That's what my Lie-algebra software package does.
First, we start with a "ring". It generalizes addition and multiplication, with addition being a group, multiplication being a monoid, and multiplication being distributive over addition. The integers under addition and multiplication are a ring.
Without a multiplicative identity (1), it's a "rng" ("rung"). Without additive inverses (negation), it's a "rig".
A commutative ring has commutative multiplication.
An integral domain is a commutative ring with the property that any two nonzero elements have a nonzero product (0 = additive identity).
A unique factorization domain is a commutative ring with a generalization of factoring into prime numbers.
A Euclidean domain is a commutative ring with a generalization of Euclid's algorithm for finding greatest common divisors.
An algebraic field is a commutative ring where multiplication of all elements but 0 is a group.
The rational numbers (Q) are a field under addition and multiplication, as are the real numbers (R) and the complex numbers (C).
All the finite fields are known. They are the "Galois fields", and they all have (prime number)^(some power) elements. They all contain fields with (prime number) elements: integers modulo (prime power) under addition and multiplication.
response:
You legit couldn’t just do 20+40=60 then 7+8= 15 and just put it together?? This must be common core math.
reply:
A lot of people (myself included) would never do that on paper but in mental math will do things like 8+8-1 for 8+7 because 8+8 immediately is 16 in your brain whereas 8+7 requires thought which will actually take a moment longer.
I am extra careful about basic operations like adding and subtracting because that's where I am most likely to trip up. I'm just better at math than I am arithmetic, which probably plays some role in why I did this:
It's neater when both numbers are odd, or both are even because then you don't end up with the half at the intermediate stage.
I tend to do it the way slim said first, but I do the above method as a check. I find it's no use doing the first method twice, because if I screw up the first time, I will just repeat the same mistake in the check.
For that one I would just do 60 + 15. I'm not always super great at arithmetic, but 7 + 8 = 15 is one of the ones I'm confident enough about to do it instantaneously without thinking. (Same with 9 + 6, for whatever reason.)
For that one I would just do 60 + 15. I'm not always super great at arithmetic, but 7 + 8 = 15 is one of the ones I'm confident enough about to do it instantaneously without thinking. (Same with 9 + 6, for whatever reason.)
same, there were a lot of frustrating nights with my dad at the dinner table with flash cards that led to a lifetime of instant head calculations of single digit times tables and addition/substraction tables. I'm grateful now...
__________________
Peering from the top of Mount Stupid
Well, darn. I don't feel so weird. I too am in the add the tens before the ones column camp. Dunno why.
It makes sense to add the most significant columns first - if you only need an approximate answer that's good enough. Sometimes I just assume that the remaining columns will total to '1' in the most significant column, and often that is pretty close.
So somebody says, "We drove three hundred and blah-blah miles yesterday, and another four hundred and something-something miles today", and you just think, "3 + 4 + 1 = 8, so that's about eight hundred miles in total."
Re: Calling all Math Geeks
Linear Mode
