1

Background: I'm working on a paper on high level synthesis, a method which combines the use of programming with digital circuit design. One of the methods I want to explain is called loop unrolling which makes use of concurrency to speed up execution, by duplicating the processing elements.

Unrolling can only be done on any function iff there is no internal relation between iterations, an example of a function with this property would be vector multiplication. My best guess would be something along the lines of $ g \triangleq \{f \in ?? | \forall n \in \mathbb{N}: f[N] does\ not\ contain\ a\ term\ for\ f[N-n]\}$.

Is there a standard or good notation to describe the set of functions which do not contain a recursive term?

Edit: I originally accepted the answer as I could see that there was a slight mismatch between the question as a whole and the formulation of the question in the final paragraph. The previously accepted answer did answer the question as written, although not as intended. I'll clear it up a bit more, apologies for the mess.

Ólafur Dagur Skúlason
  • 23
  • 2
    As far as I know, there's no notation for this, because "what terms a function's definition has" are not inherently part of the function. You can define many functions either with or without recursion, and they're the same function either way -- so this isn't really a meaningful notion in mathematics. – Deusovi Apr 01 '19 at 17:33
  • 1
    I do want to point out that it is a meaningful notion in Computer Science because if a function can only be calculated recursively, it cannot be parallelized, which generally means computational complexity increases massively. Calculating Fibonacci using the $F_n=F_{n-1}+F_{n-2}$ definition runs in $O(\left(\frac43\right)^n)$ time, while dynamic programming runs in $O(n)$ time (which is slightly recursive), while Binet's formula/matrix exponentiation can run in $O(\log n)$ time using a completely nonrecursive formula. – AlgorithmsX Apr 01 '19 at 17:40

1 Answers1

2

As far as I know, there is no specific notation.

You might write something like

$$f[N]:=\alpha(\{a,b,c,\cdots\})=\alpha(V)$$

where $\alpha$ denotes the expression (or more generally the algorithm) that evaluates the value to be assigned to $f[N]$, and $V=\{a,b,c,\cdots\}$ is the set of variables that appear explicitly in $\alpha$.

Then the absence of a dependency is expressed by

$$f[N-n]\notin V.$$

On second thoughts, though your notation seems to imply an array, this is unlikely as you say $\forall n$. But then, saying that the value of $f_N$ (at iteration $N$) depends on the value $f_{N-n}$ (at iteration $N-n$) only makes sense if the process has enough memory (variables) to realize such a dependency. This is a much more complicated situation.

An example would be a running sum on, say, three elements,

i= 0
a= b= c= s= 0
while True:
    a= b; b= c; c= K[i]
    i= i + 1
    s= s - a + c
  • Your second thoughts are pretty much what I want to describe. As I mentioned in the question vector operations are common applications for this technique as although each step of the procedure uses the original vectors, by splitting them on the index and treating each indexed value separately.

    Using dot product as an example, $\sum_{n=0}^{N} (a_n * b_n)$ the inner term of the definition can be done concurrently.

     – Ólafur Dagur Skúlason Apr 03 '19 at 06:17
  • I was too late to edit: Using dot product as an example, $ c = \sum_{n=0}^{N} (a_n * b_n)$ the inner term of the definition does not contain a term for $ c_{N-n} $ and fulfills the requirement. I'm going to accept the answer as I accept that the requirements do not properly apply in mathematics. – Ólafur Dagur Skúlason Apr 03 '19 at 06:31
  • @ÓlafurDagurSkúlason: the case of the dot product is exactly my first thought, not at all the second. In your question there is a large ambiguity between the indexes of an array and the iteration number. –  Apr 03 '19 at 09:09