Fibonacci数和Lucas数的联合迭代算法

针对超大Fibonacci数和Lucas数的计算问题,提出一种Fibonacci-Lucas数联合迭代算法,在单次循环中选择二倍步长的方式,采用交替计算Fibonacci数和Lucas数的方法,减低超大数迭代算式的复杂度,提高程序的计算效率。实验结果表明,该算法运行时间比现有的矩阵迭代算法更短。     

A simple and fast algorithm for computing exponentials of power series

As was initially shown by Brent, exponentials of truncated power series can be computed using a constant number of polynomial multiplications. This note gives a relatively simple algorithm with a low constant factor.     

Inversion of the generalized Fibonacci matrix by convolution

A convolution formula containing the generalized Fibonacci numbers and applications of this formula are investigated. Starting from the convolution formula, we derive combinatorial identities involving generalized and usual Fibonacci numbers, as well as the Lucas numbers. The inversion of a lower triangular matrix and the generalized inversion of strictly lower triangular Toeplitz matrix whose non-zero elements are generalized Fibonacci numbers are considered.     

Multiset rewriting over Fibonacci and Tribonacci numbers

We show how techniques from the formal logic, can be applied directly to the problems studied completely independently in the world of combinatorics, the theory of integer partitions. We characterize equinumerous partition ideals in terms of the minimal elements generating the complementary order filters. Here we apply a general rewriting methodology to the case of filters having overlapping minimal elements. In addition to a ‘bijective proof ’ for Zeckendorf-like theorems – that every positive integer is uniquely representable within the Fibonacci, Tribonacci and k-Bonacci numeration systems, we establish ‘bijective proofs’ for a new series of partition identities related to Fibonacci, Tribonacci and k-step Fibonacci numbers. The main result is proved with the help of a multiset rewriting system such that the system itself and the system consisting of its reverse rewriting rules, both have the Church–Rosser property, which provides an explicit bijection between partitions of two different types (represented by the two normal forms).     

Fibonacci multi-modal optimization algorithm in noisy environment

Noises are very common in practical optimization problems. It will cause interference on optimization algorithms and thus makes the algorithms difficult to find a true global extreme point and multiple local extreme points. For the problem, this paper proposes a Fibonacci multi-modal optimization (FMO) algorithm. Firstly, the proposed algorithm alternates between global search and local optimization in order not to fall into local optimum points and to retain multiple optimum points. And then, a Fibonacci regional scaling criterion is proposed in the FMO algorithm to alleviate the effects of noise, and the position of optimum point is determined according to its probability distribution under noise interference. In experiments, we evaluate the performance of the proposed FMO algorithm through 35 benchmark functions. The experimental results show that compared with Particle Swarm Optimization (PSO) algorithm, three improved versions of PSO, and Genetic algorithm (GA), the proposed FMO algorithm can gain more accurate location of optimum point and more global and local extreme points under noisy environment. Finally, an example of practical optimization in radio spectrum monitoring is used to show the performance of the FMO algorithm.     

H.264运动估计算法UMHexagonS的斐波纳契数列优化

针对H.264运动估计算法UMHexagonS搜索步长和搜索模板中存在的使用固定搜索步长和搜索点冗余的不足,结合斐波那契数列和中心偏置特性对其进行改进。新算法使用斐波那契数列的递进关系确定UMHexagonS算法的搜索步长,其次删除UMHexagonS算法中存在计算冗余的搜索点,最后结合中心偏置特性对UMHexagonS算法的大六边形搜索模板进行了修改。实验结果表明,新算法在保持UMHexagonS算法的比特率和峰值信噪比(PSNR)的情况下缩短了运动估计时间,并且随着图像像素、图像复杂度和搜索范围的提高,运动估计时间越来越短。新算法在搜索范围为64的情况下,平均缩短了23.82%的运动估计时间。     

Performance evaluation of uniform linear array for adaptive beamforming using a novel Fibonacci branch algorithm

A new metaheuristic algorithm Fibonacci branch search (FBS) based on two innovative criteria rules, tree's branches fundamental structure and interactive searching rules, was introduced in this paper and applied to adaptive beamforming (ABF) field for uniform linear array. The global optima in search space can be reached by FBS during the searching process by the fitness evaluation of optimization rules. In this mode, two types of multidimensional points are to construct the branch structure of FBS based on shortening fraction selected by Fibonacci series. Then, the interactive local optimization and global searching rules are implemented alternately to obtain the optimal solutions, avoiding the search points trapping and stagnating in the local optimum. The performance of global searching ability of FBS has been evaluated by standard benchmark functions. It is also used here to construct an ABF technique as a practical issue to improve the nulling level. The simulation results of implemetation of FBS are compared with the five well‐known heuristic optimization algorithms and verfied the superior of the proposed FBS approach in both locating the global optimal solution and higher precision of nulling improvement in the ABF.     

A computational method for simulating growth patterns in unicell propagation

The modelling of natural phenomena through the use of computer-generated graphics has attracted much interest recently. It is believed that such methods will lead to new breakthroughs in understanding nature. One of the most popular methods used is the cell automata method, where cells are made to propagate and form cellular patterns according to certain predefined rules. Although much of the work in this area is for recreational purposes, as in the Game of Life, there can be more serious aspects to it. One of these is in the use of such methods to predict and simulate the growth behaviour of cell clusters in real-life situations. In this study, an attempt is made to formalise certain rules for modelling the growth characteristics of unicell populations. The methodology proposed models three fundamental factors: first, the generic propagational characteristics of a cell; second, the effect of adverse factors to growth; and, third, the effect of spatial constraints. The first two factors, relating to the population of a cell colony, can be modelled mathematically; the third factor determines the visual appearance of the cell colony. Patterns resulting from some computational simulations are presented and discussed.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

A simple linear algorithm for intersecting convex polygons

LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.     

A fast algorithm for an envelope construction of a huge set of topologically consistent polygons

This paper describes an efficient algorithm for the determination of an envelope of a set of polygons. The polygons have to be aligned along their borders – the case which, for example, appears in geographic information systems. The edges, which belong to two neighbouring polygons, are called twin edges, and are eliminated first. To accelerate the geometric search, a two-level uniform plane subdivision structure is proposed. The remaining non-twin edges belong to the envelope, and they have to be joined to form the simple polygons at the end. For this task, a new algorithm has been developed. At the end, spatial relationships between resulting polygons are established. The whole algorithm for envelope determination works in expected time O(n log n) using O(n) memory space, where n is the total number of edges belonging to the input polygons. In the last part of the paper, practical results using data from a geographical database are considered.     

A simple and fast algorithm for K-medoids clustering

This paper proposes a new algorithm for K-medoids clustering which runs like the K-means algorithm and tests several methods for selecting initial medoids. The proposed algorithm calculates the distance matrix once and uses it for finding new medoids at every iterative step. To evaluate the proposed algorithm, we use some real and artificial data sets and compare with the results of other algorithms in terms of the adjusted Rand index. Experimental results show that the proposed algorithm takes a significantly reduced time in computation with comparable performance against the partitioning around medoids.     

A straightforward algorithm for computing the medial axis of a simple polygon

A new algorithm for computing the medial axis of a simple polygon is presented. Although the algorithm runs in O(kN) time where k is the hierarchy of the Voronoi diagram of the polygon ranging from O(N) to O(logN) it is simple to implement and it does not require the complex data-structures required for the faster methods. This is an important factor in many applications of the medial axis.     

A simple linear hidden-line algorithm for star-shaped polygons

A very simple, linear-running-time algorithm is presented for solving the hidden-line problem for star-shaped polygons. The algorithm first decomposes the visibility regions into edge-visible polygons and then solves the hidden-line problem for these simpler polygons. In addition to simplicity the algorithm possesses the virtue of affording a very easy proof of correctness. Some applications where this problem arises are mentioned.     

基于广义变参Fibonacci混沌系统的压缩感知测量矩阵构造算法

针对常见混沌映射随机性不高、序列元素相关性较强、构造测量矩阵元素需间隔采样来满足数据统计的独立性等问题,通过级联量子Logistic混沌系统和广义Fibonacci数列构造一种新的复合混沌系统.在信息熵、空间特性和相关系数等方面对不同混沌测量矩阵进行定量分析,验证了提出的混沌系统具有遍历性和很强的混沌特性要求,序列元素...     

A Fibonacci Search technique for a class of multivariable functions and ODEs

In this paper, a robust technique which uses the Fibonacci Search is developed using the notion of hyperplanes for a class of multivariable functions. The paper also finds other area of application in differential equations. Numerical examples abound to demonstrate the efficiency of our technique.     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.