In a recent paper, Frank Ruskey asked whether every linear recurrent sequence can occur in some solution of a meta-Fibonacci sequence. In this paper, we consider the natural generalization of meta-Fibonacci recurrence...
详细信息
In a recent paper, Frank Ruskey asked whether every linear recurrent sequence can occur in some solution of a meta-Fibonacci sequence. In this paper, we consider the natural generalization of meta-Fibonacci recurrences to more than two terms. In this context, we show, using an explicit construction, that any sequence satisfying a linear recurrence with positive coefficients occurs as an evenly-spaced subsequence in some generalized meta-Fibonacci sequence.
We explore the nature of the solution space for the Golomb nested recursion . On this solution space, we define a natural equivalence relation and restrict our attention to non-equivalent solutions. We describe and pr...
详细信息
We explore the nature of the solution space for the Golomb nested recursion . On this solution space, we define a natural equivalence relation and restrict our attention to non-equivalent solutions. We describe and prove an algorithm that determines whether a given set of initial conditions generates a solution. Up to equivalence, there is a unique solution whose forward differences are eventually either 0 or 1, namely, the Golomb sequence , generated by the initial condition . This sequence is asymptotic to;we conjecture that this is true of every solution. We further conjecture that each solution has what we call a generational structure that abstracts combinatorial properties of . It appears that for any given solution, its generations are composed of only a finite number of building blocks.
There has been a significant amount of effort invested in designing scheduling transformations such as loop tiling and loop fusion that rearrange the execution of dynamic instances of loop nests to place operations th...
详细信息
ISBN:
(纸本)9781450344654
There has been a significant amount of effort invested in designing scheduling transformations such as loop tiling and loop fusion that rearrange the execution of dynamic instances of loop nests to place operations that access the same data close together temporally. In recent years, there has been interest in designing similar transformations that operate on recursive programs, but until now these transformations have only considered simple scenarios: multiple recursions to be fused, or a recursionnested inside a simple loop. This paper develops the first set of scheduling transformations for nested recursions: recursive methods that call other recursive methods. These are the recursive analog to nested loops. We present a transformation called recursion twisting that automatically improves locality at all levels of the memory hierarchy, and show that this transformation can yield substantial performance improvements across several benchmarks that exhibit nested recursion.
The design of many tail recursive algorithms can involve thinking about the status of variables and parameters, and how these change with execution flow. In other words, tail recursion is closely related to iteration ...
详细信息
ISBN:
(纸本)9781605588209
The design of many tail recursive algorithms can involve thinking about the status of variables and parameters, and how these change with execution flow. In other words, tail recursion is closely related to iteration and imperative programming. However, it is possible to derive tail recursive functions by exclusively using concepts inherent in recursion, such as declarative programming, induction, or problem decomposition. This paper proposes a simple methodology for designing tail recursion functions by using a declarative approach and the concept of function generalization. We have carried out an evaluation of the technique with second and third-year computer science students. Results suggest that this new point of view improves students' ability to design tail recursive programs, helps them understand the distinction between the imperative and declarative paradigms, and may reinforce their programming skills in general. Furthermore, students found the methodology easy to learn and apply, simpler than more sophisticated formal methods, and described it as fast and methodic or mechanical, as it involves a sequence of well-defined steps.
Datalog is a declarative programming language that has gained popularity in various domains due to its simplicity, expressiveness, and efficiency. But "pure" Datalog is limited to monotone queries, and canno...
详细信息
Datalog is a declarative programming language that has gained popularity in various domains due to its simplicity, expressiveness, and efficiency. But "pure" Datalog is limited to monotone queries, and cannot be used in most practical applications. For that reason, newer systems are relaxing the language by allowing non-monotone queries to be freely combined with recursion. But by departing from the elegant fixpoint semantics of pure datalog, these systems often result in inefficient query execution, for example they perform redundant computations, or use redundant storage. In this paper, we propose Temporel, a system that allows recursion to be freely combined with non-monotone operators. Temporel optimizes the program by compiling it into a novel intermediate representation that we call TempoDL. Our experimental results show that our system outperforms a state-of-the-art Datalog engine as well as a vectorized and a compiled in-memory database system for a wide range of applications from machine learning to graph processing.
暂无评论