基于VC的回文数猜想检验算法

回文数猜想是一个著名的数学问题,尤其是自然数196,至今尚未证实是否是Lychrel数。为了在32位计算机上实现检验回文数猜想的196算法,提出在VC＋＋平台下用字符串来实现。给出了算法的具体形式,对程序中每一个步骤予以详细说明。最后实验证实了算法突破了Windows XP的32位字长限制。     

用易语言编写数字黑洞猜想检验程序

数字黑洞是数学中的一种奇妙现象,采用计算机编程的方法可有效解决诸多此类猜想的检验问题,而且这种检验是在计算机所容许的最大数值范围内作出的,这无疑使得该类猜想离百分之百真命题的距离仅差一步之遥,其探究意义尤为深远.所给出的被动式与主动式两个易语言程序,都是在易语言软件环境中运行通过的,将其拷贝下来便可直接使用.     

高位水仙花数快速求解算法

为了处理超出计算机字长范围的整数,需要构造合适的数据结构,用以存储超大数据。本文研究水仙花数的特征,结合排列组合和函数单调性等相关理论,借助“栈”后进先出的特点,利用动态数组存储超大整数。这种方法突破了传统设计思路仅考虑有限长度范围内的整型数据处理的约束,使得寻找正整数范围内的水仙花数的计算工作量呈几何级减少,达到了在较短时间内快速寻找正整数集合内所有水仙花数的目的,对超大整数的处理具有较好的参考作用。     

超高精度数的算法研究

讨论了超高精度数在计算机数值运算中的算法，提出了通过利用计算机内部变量间的转换方式以及利用数组存储变量，实现超高精度数的输入、输出、存储和计算的方法。     

关联维数的并行求解算法

关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要,过去的改造算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数,其应用范围和性能改善程度是有限的。本文给出了两个并行算法：基于PRAM模型的花费O(N^2／p logp)时间p个处理机的算法,和基于LARPBS模型的花费O(N^2p)时间p个处理机的算法。相对纯理论的PRAM算法,LARPBS算法是实际可行的,它是目前时间复杂度最低的算法,并且是最优可扩展和成长最优的。     

Catalan数在算法分析中的应用

如果一个问题其数学模型与Catalan 数的递推公式相符合,就可以利用Catalan数的某些结论来解决此问题.可使看上去比较复杂的问题的解决变得比较容易.有些算法的分析可能比较复杂,也可以利用组合数学的某些结论来进行分析.     

基于DNA算法的独立数问题的求解

在构造了一种链接链及一种新型的“类发夹式”探针的基础上,给出了图的独立数问题的一种DNA算法。利用顶点的简单编码及链接链,该算法直接生成数据池,使用常规的生物操作即可完成解空间的产生及最终解的分离。     

代数数根界的一个有效算法及其实现

得出了代数数根界的一个基于结式的有效实现算法,并且已用计算机代数系统MAPLE在微机上实现。用这种新的实现算法,计算了文献[1,7]中的几个代数表达式的根界。数值结果表明,它比Scheinerman在文献[1]中所给出的根界以及BFMS界具有更好的效果。     

利用剩余数制简化DNA算术运算

在DNA算术运算的理论模型中,普遍应用固定基数制,比如二进制、三进制。但是由于受到进位的影响,难以实现并行运算。基于Adleman-Lipton模型,分析了剩余数制的基本原理,改进了整数的DNA链表示,并将其应用于DNA算术运算,给出了剩余数制下进行DNA算术运算的算法模型。由于在剩余数制中,算术运算（加、减、乘）在剩余位之间无须进行进位计算,故可以降低运算过程的复杂度,而且有利于进行各个剩余位上的并行计算。     

Triplex: A system for interval arithmetic

Triplex is a language which supports interval arithmetic. The interval is represented by a triple. That is, the end points of the interval plus the value that real computer arithmetic would calculate. The intervals are used to bound the errors that occur in real calculations. The paper describes how they may be implemented.     

三维场景仿真过程中底层算法的优化研究

三维场景是所有三维仿真的基础,为三维形体提供一个活动场所或背景空间,在模拟、虚拟现实、游戏等众多领域中有着广泛应用。目前大量的研究侧重于不同地形生成理论与算法的优化研究,在底层算法方面侧偏爱于列表算法实现。结合三维场景生成实践,在运用常见地形算法基础上,立足OpenGL本身算法的优化,提出运用顶点数组算法来优化三维场景的快速生成,与列表算法比较,进一步简化了算法实现,提高了算法效率。     

分布算术并行结构设计研究

提出一种基于DA实现的可扩展的阵列结构,通过对阵列的配置使其具有良好的扩展能力以及并行处理的高效特性。该结构与传统的采用ASIC电路的实现方式相比,较好地解决了ASIC电路中阶数、数据字宽不可自适应调整以及存储量需求较大、吞吐量偏低的问题。最后在实现代价和性能方面与典型结构进行了比较,证明了该结构存储量需求小,运算时间少,具有较好的性价比。     

Rational arithmetic for minicomputers

A representation for numbers using two computer words is discussed, where the value represented is the ratio of the corresponding integers. This allows for better dynamic range and relative accuracy than single-precision fixed point, yet is less costly than floating point arithmetic. The scheme is easy to implement and particularly well suited for minicomputer applications that call for a great deal of numerical compulation. The techniques described have been used to implement a mathematical function subroutine package for a minicomputer as well as a number of applications programs in the machine vision and machine manipulation area.     

Implementation independent arithmetic: Speculation for discussion

The specification of a truly portable implementation independent programming language requires that digital arithmetic be specified in an implementation independent manner. Variable length storage is proposed for digital numbers. Linked storage and linked overflow storage are proposed so as to enable the use of variable length numbers. It is suggested that significant digit arithmetic be used for single numbers and interval arithmetic be used for interval pairs. The question is put to numerical mathematicians to specify the decision rules to be used in deciding on the number of digits to be retained when computing in either the significant digit mode or in the interval mode. The question is also raised as to what other arithmetic modes should be provided for. The speculation is offered not for the purposes of suggesting useful hardware design techniques but rather to indicate feasibility of some design. If the implementation independent arithmetic is considered feasible, then language designers can design a language freed from present hardware restrictions.     

New uses of linear arithmetic in automated theorem proving by induction

Zhang, Kapur, and Krishnamoorthy introduced a cover set method for designing induction schemes for automating proofs by induction from specifications expressed as equations and conditional equations. This method has been implemented in the theorem prover Rewrite Rule Laboratory (RRL) and a proof management system Tecton built on top of RRL, and it has been used to prove many nontrivial theorems and reason about sequential as well as parallel programs. The cover set method is based on the assumption that a function symbol is defined by using a finite set of terminating (conditional or unconditional) rewrite rules. The termination ordering employed in orienting the rules is used to perform proofs by well-founded induction. The left sides of the rules are used to design different cases of an induction sheme, and recursive calls to the function made in the right side can be used to design appropriate instantiations for generating induction hypotheses. A weakness of this method is that it relies on syntactic unification for generating an induction scheme for a conjecture. This paper goes a step further by proposing semantic analysis for generating an induction scheme for a conjecture from a cover set. We discuss the use of a decision procedure for Presburger arithmetic (quantifier-free theory of numbers with the addition operation and relational predicates >, <, ≠, =, ⩾, ⩽) for performing semantic analysis about numbers. The decision procedure is used to generate appropriate induction schemes for a conjecture by using cover sets of function taking numbers as arguments. This extension of the cover set method automates proofs of many theorems that otherwise require human guidance and hints. The effectiveness of the method is demonstrated by using some examples that commonly arise in reasoning about specifications and programs. It is also shown how semantic analysis using a Presburger arithmetic decision procedure can be used for checking the completeness of a cover set of a function defined by using operations such as + and — on numbers. With this check, many function definitions used in a proof of the prime factorization theorem stating that every number can be factored uniquely into prime factors, which had to be checked manually, an now be checked automatically in RRL. The use of the decision procedure for guiding generalization for generating conjectures and merging induction schemes is also illustrated. Partially supported by the National Science Foundation Grant No. CCR-9303394 and subcontract CB0249 of SRI contract MDA904-92-C-5186 with The Maryland Procurement Office.     

基于纹理特征的指纹识别算法

基于纹理特征的指纹识别方法,具有计算量小的特点。本文对该指纹识别算法进行了系统研究,提出了一套新颖的方向图修正算法,对于噪声相对较小的情况具有良好的效果。本文对多窗口法求块方向图给出了减少运算量的方法;在方向滤波器设计方面,给出了一个方向滤波器的闭合等式,可以简化方向滤波器设计,大大减少运算量,并取得了较好的增强效果;在中心点求取方面,提出了一种新的粗搜索算法,可以减少计算量,加快中心区域搜索速度。     

A sufficient condition for non-overestimation in interval arithmetic

The range of an arithmetic expression on an interval can be estimated by evaluating the expression using interval arithmetic. This gives always a superset of the range, which is usually proper. However, there are cases where no overestimation error occurs. The subject of this paper is to study such cases systematically and to give a sufficient condition when interval evaluation yields the exact range. Testing the condition is inexpensive: Given the intermediate values which are obtained during the evaluation of the expression, only some comparisons and bookkeeping but no additional arithmetic operations need to be performed. We show that for certain classes of expressions there is no overestimation if the input interval has a sufficiently large distance to zero. Formulae for the minimal distance are derived for polynomials in Horner form and in factorized form.