Ok so I want to have the sequence 0,1,0,1,0,1,...
Its generated by this: 1/2 (1 + (-1)^n)
Now I want the Sequence 0,1,2,0,1,2,0,1,2,...
Wolfram Alpha tells me the function to get this is a_n = (n + 2) mod 3
BUT in my program I can't to use MOD or IF(F) because it slows stuff down too much, I want a nice function like I had before. Recursion is no problem. Wat do?
Other urls found in this thread:
mathworks.com
twitter.com
a mod n = a - (n * int(a/n))
Thanks for the answer but casting a division which could result into a float/double into an integer is just as bad using mod. If you want to use division it have to result in an integer. No casting allowed.
Are you allowed to set the first three as 0, 1, 2 and then say: a_n = n-3 ?
You can't make a sequence with a cycle greater than 2 without division and modular arithmetic in the real numbers. If you want to use exponentiation to create a sequence that cycles after 3 steps, then you need complex numbers. You can use the formula [(-0.5 + 0.5*i*sqrt(3))^(n-1) - (-0.5 - 0.5*i*sqrt(3))^(n-1)]/(i*sqrt(3)) + 1. This is assuming your index starts at 0.
trips of truth.
good solution
but a modular solution may be slower than that route
of course, the division by i*sqrt(3) is the same as multiplication by 1/(i*sqrt(3)), so this is still just multiplication.
excuse me:
modular will probably be quicker than the one with all the imaginary square roots
>of course, the root operation i*sqrt(3) is the same as exponent i*3**(0.5), so this is still just exponentiation
Yes, I know basic mathematics as well user
Depends on the hardware. Two and four quadrant multiplication can be done very fast.
Overall, this method isn't very good. Testing this out in Matlab, it is apparent that every time the sequence is supposed to be 0, the floating point representation contains some small remnants due to either the cancellation from subtraction, or because the finite precision machine can't actually do computations with the true value of sqrt(3). The error becomes noticeable for all terms of the sequence at the 200th term, or before. If this process were to be implemented, then it would need to be symbolic, and recursively defined. Really, there is nothing wrong with if statements, what I suspect is happening here is that you are using naive numerical methods. Take the tail recursion method, for example. The tail recursion method is a method where the initial call contains 0, 1, 2 and an integer n. When n gets incremented by -1, then the dummy's value copies the leftmost slot, the leftmost slot copies the middle slot, the middle slot copies the rightmost slot, and the rightmost slot copies the dummy. This method is shit because there are exponentially more steps per symbol in the input (because n is expressed in base 2 or greater). To get around this, we can use a more advanced method. If you want to find n mod 3, then we will use a tripling method. Essentially what we are going to do is compute powers of 3 (in base 2) and compare the number to the number n until we find a power of 3 that is larger than, or equal to n. Once we find it, then we will subtract the largest possible power of 3 as many times as possible (0, 1 or 2 times), then divide down to the next largest power of 3 (better yet, you could just keep a table of powers of 3 stored in memory, and just reference it), and subtract it as many times as possible, and so on and so forth, until we are down to 3^1. When we can't subtract any more copies of 3^1, then the remainder is n mod 3. This method is way better, because the number of steps goes up linearly, as the input size increases.
note, computing 3^(n+1) using just 3^n can be done in 2 addition steps, so that part of the algorithm works in linear time.
>You can't make a sequence with a cycle greater than 2 without division and modular arithmetic in the real numbers.
Yes I can you fucking piggot
(-1)^ [ n(n+1)/2]
(a_n, a_n+1) = ((-1)^n, (-1)^n), n starts at 1
The sequence still has cycle 2
*a_2n, and a_2n+1
a(n) = 3 - a(n-1) - a(n-2) for n > 1.
a(n) = 1 - 0^((-1)^(n/3)-(-1)^n) + 0^((-1)^((n+1)/3)+(-1)^n).
a(n) = 1 + (-1)^((2*n+4)/3)/3 + (-1)^((-2*n-4)/3)/3 + 2*(-1)^((2*n+2)/3)/3 + 2*(-1)^((-2*n-2)/3)/3.
You know guys, in the context of how a computer actually works, it's easier to generate the sequence 0,1,2,0,1,2... than it is to generate the sequence n = 1,2,3,4,5,6...
For example.
Take n
Read the last two bits of n = 00,01,11,00,01
Done
Oh right. 3.
Well fuck n, use a shift register jesus
>I can't to use MOD or IF(F) because it slows stuff down too much
These would normally be very fast. First, make sure you really know what's fast and slow by actually testing it.
>Matlab
Try some of these:
mathworks.com
a_n = 1 + (1-2*cos(2*Pi*(n-1)/3)) * sin(2*Pi*(n-1)/3)) / sqrt(3)
The tripling method is kind of shit because you have to store the powers of 3, but there is a better way. Because the machine works in binary, the doubling method works way better because dividing by 2 takes almost no time. In particular, you would start with 3, compare 3 to n, and if 3 is too small, you double it. Compare again, and, if it is too small, double it. Once the doubling method gets a larger value than n, then the division step will only involve removing a 0 from the end of the number.