A mathematical function for counting forwards then backwards

Question

Is there a mathematical function for counting forwards then backwards though a number range. e.g.

Range of 0-10

The number 7 would equal 7

The number 11 would equal 9

The number 23 would equal 3

So the numbers are counting all the way to the upper limit then counting back down and then back up again and so on.

I come across this requirement a lot in programming and was wondering if there was a typical math formula/function for calculating this?

The answer you chose is a very bad idea in programming, because it is simply impossible to compute $π,\sin,\arcsin$ exactly. Furthermore, my answer gives the most efficient way to do what you want, since it only involves basic integer arithmetic. — user21820, Dec 01 '17 at 04:28
Yeah, for programming a simple piecewise defined function makes the most sense. — Jared, Dec 01 '17 at 04:29
@Jared: Yeap piecewise is the way to go for more complicated stuff, but here the two methods I gave in my answer will work well (no conditionals or lookup tables). — user21820, Dec 01 '17 at 04:30

mathreadler · Answer 1 · 2017-12-01T22:04:24.773

Yes, just use the cyclic group by first building a representation matrix of its generating element : a circulant matrix

$${\bf C} = \left[\begin{array}{cccccc}0&1&0&0&0&0\\0&0&1&0&0&0\\0&0&0&1&0&0\\0&0&0&0&1&0\\0&0&0&0&0&1\\1& 0&0&0&0&0\end{array}\right]$$

Now let first number be represented by ${\bf v} = [1,0,0,0,0,0]^T$. Then next number is $\bf Cv$, third number is ${\bf C}^2 \bf v$ and so on. Finally assign the value for each position to a column vector $w$. For your example you will want $w_1 = w_N$, $w_2 = w_{N-1}$ and so on, and the value of number at position $k$ of your sequence will be the scalar product:

$${\bf w}^T {\bf C}^k {\bf v}$$

It will be more general than sines and arcsines as you can prescribe any sequence of numbers in $\bf w$.

An example of ${\bf w} = [1,2,3,3,2,1]^T$ will give 1,2,3,3,2,1 in that order if you increase $k=0,1,2,3,4,5$, so you can explicitly enter the numbers you want to have in the sequence into the vector.

If you want to be even fancier/advanced you can construct ${\bf w}^T$ using the following:

$${\bf w}^T = [1,2,3]\left[\begin{array}{cccccc}1&0&0&0&0&1\\0&1&0&0&1&0\\0&0&1&1&0&0\end{array}\right]$$

In general the matrix will be an identity followed by a "opposite diagonal" matrix filled with ones.

score 1 · Answer 2 · answered Dec 01 '17 at 04:26

1

Let $n$ be the index. Then $(n \bmod 2k)$ cycles every $2k$, but you want it to go up then come down halfway through each cycle. So reflect it at the maximum height. Reflection at height $0$ on the top is $( x \mapsto |x| )$, so reflection at height $(k-1)$ on the bottom is $( x \mapsto k-1-|k-1-x| )$. Put these together to get what you want.

With a little more thinking, start with $(n \bmod 2k-k)$ and then simply reflect it at height $0$ on the top. You get $| n \bmod 2k - k |$. Now all you need is to shift the sequence, since right now it goes down first before going up.

answered Dec 01 '17 at 04:26

user21820

57,693
9
98
256

Yes you can implement the matrix solution below with pointer arithmetics like this. As long as will fit in cpu cache it will be really difficult to beat by any other method, at least in terms of speed. – mathreadler Dec 03 '17 at 14:14
@mathreadler: Your comment does not really make sense. My answer has nothing to do with pointer arithmetic. And if you read the question as stated, it is obvious the asker wants a general solution for arbitrary integer $k$. Your solution works only for really tiny fixed $k$. As for arbitrary sequences, my solution can be easily adapted by using "$c[n] \bmod 2k$" instead of "$n \bmod 2k$", which would not only be faster than yours but also trivially implemented. – user21820 Dec 03 '17 at 14:23
Yes you are right I see now that I misread your question, I assumed that you stored the values in memory and cycled through them. – mathreadler Dec 03 '17 at 14:26
@mathreadler: Yup that is also possible, but unnecessary in the case of this question. Too bad the asker accepted a non-answer (it won't even work after a while). – user21820 Dec 03 '17 at 14:28
it depends on how you interpret counting up and down. If it always must be by some fixed k each step or not. 1,2,3,5 for example is counting up in the sense each new number is larger than the previous. But it is just not counting up by any fixed rate. Yes I also don't like the sin+arcsin but mostly because its implementation is often quite slow on CPUs. – mathreadler Dec 03 '17 at 14:32
@mathreadler The question explicitly says "counting forwards then backwards though a number range". That is rather unambiguous and hence my answer. As for the trigonometric formula, it's not a matter of speed as opposed to absolutely unavoidable numerical inaccuracy, which requires higher computational complexity as the input grows. – user21820 Dec 03 '17 at 16:24
Any numerical inaccuracy depends solely on the implementation. The person giving the answer said nothing about which method to calculate sin or arcsin should be used and there exist plenty different ones. However there does not exist any particularly fast one. I would consider that wording quite sloppy anyway. – mathreadler Dec 03 '17 at 17:44

actinidia · Accepted Answer · 2017-11-28T23:09:02.773

-1

The parent function of your function is a triangle wave. Indeed, we have

$$P(x) = \frac{2a}\pi \arcsin\big(\sin\big(\frac{2 \pi}p x\big) \big)$$

So let $a = 10$ and $p = 40$, then take the absolute value to get your function:

$$f(x) = \Big|\frac{20}\pi \arcsin\big(\sin\big(\frac{\pi}{20} x\big) \big)\Big|$$ where $|x|$ is the absolute value of $x$.

edited Nov 28 '17 at 23:09

answered Nov 28 '17 at 23:03

actinidia

3,365

Awesome... I don't understand math formulas but I was able to look up what a triangle wave was and that gave me the solution. – McShaman Nov 28 '17 at 23:20
1

I would consider this a flagrant abuse of the $\arcsin$ function. – Jared Dec 01 '17 at 04:30
@Jared What's the point of inverse trigonometric functions if we aren't allowed to use them? :P More seriously, does the use of $\arcsin x$ present a practical issue? – actinidia Dec 01 '17 at 04:33
@TiwaAina The point of them is to find angles--that's not how you're using it. This would be like me saying $|x|= \sqrt{x^2}$, it's "technically" correct for most calculators but I wouldn't consider it correct because you have to assume a particular branch of the square root function. – Jared Dec 01 '17 at 04:34
2

@TiwaAina From a programming standpoint, yes, the the $\arcsin$ call and $\sin$ call (not to mention all of the unnecessary multiplications and divisions) are extremely expensive calls when there are much more efficient ways (as have been presented) to compute the same thing. – Jared Dec 01 '17 at 04:37
@Jared Ah, I suppose you have a point. When he asked for a typical function, though, I understood that to mean "elementary function allowed, conditional functions disallowed." Also, he mentioned counting forwards then backwards and gave integer examples, so accuracy shouldn't be an issue. Furthermore, the efficiency differential is surely negligible, since "log, exp, and trig functions are $O(M(n) \log n)$ (in fact they're all calculated from log), where $M(n)$ is the cost of multiplication (theoretically $O(n\log n 2^{\log^*n})$ by Furer's algorithm)." – actinidia Dec 01 '17 at 05:22
Source for the above comment: – actinidia Dec 01 '17 at 05:23
2

@TiwaAina I can't make heads or tails of that statement (for one the statement is wrong, Fürer's algorithm is $O\left(nlog(n)2^{O\left(log^*(n)\right)}\right)$, source). As best I can tell, that means it's essentially $O\left(n^2log(n)\right)$--which is significantly less efficient than $O(n)$ solutions that have been presented. And further, you're talking about integer computations--these would undoubtedly be floating point operations. – Jared Dec 01 '17 at 06:12
@TiwaAina: My solution uses just one absolute value function call, and only integer arithmetic operations besides that. This is constant time. You should actually write a program to compute $\sin$ before you make wrong claims about the practical efficiency of your solution, which is nowhere near constant time. Worse still, unless you do something extremely clever, your solution will get slower and slower as $x$ increases... – user21820 Dec 01 '17 at 06:23
1

@TiwaAina I took your suggestion and, no surprise, your method was considerably slower: $\begin{matrix}\text{size} & \text{arcsin} & \text{piecewise} \ 1,000 & 0.936\ ms & 0.067\ ms \ 10,000 & 8.694\ ms & 0.763\ ms \ 100,000 & 84.64\ ms & 1.04\ ms \ 1,000,000 & 828.6\ ms & 6.6\ ms \ 10,000,000 & 8,206\ ms & 64\ ms\end{matrix}$.$\$ Which shows a nearly $100$X slow-down. And I don't think you appreciate the fact that this is a function call and gets compounded depending on the particular algorithm (so for an $O(n^2)$ algorithm, you'll get a $100^2 = 10,000$X slow-down). – Jared Dec 01 '17 at 07:25
1

@TiwaAina And if you're wondering: here was the function call for the arcsin: return (int) Math.round(Math.abs(20.0 / Math.PI * Math.asin(Math.sin(Math.PI * x / 20.0)))); And here was the function call for the "piecewise": x %= 20; if (x <= 10) return x; // else return 20 - x; – Jared Dec 01 '17 at 07:35

A mathematical function for counting forwards then backwards

3 Answers3