Lijie Ding

Document Type

Thesis - University Access Only

Award Date

1997

Degree Name

Master of Science (MS)

Department / School

Computer Science

Abstract

For a long time, people have been baffled by trying to solve the “Perfect Square Problem". From it, more problems are inherited. The inherited perfect square problem in this paper is one example. It is stated as follows: Given any integer N, try to find positive integer A and B, such that both A2 + B2 and A2 + (B - NA) 2 are perfect squares. In this paper, two different approaches for solving the problem are introduced. The first one is the Forward-Algorithm, which takes advantage of logical common thinking and modifes Dahlquist's algorithm to demonstrate A and B. Hence, the Forward-Algorithm is easy to understand. By running its program, all solutions, if one exists, can be obtained, including the smallest one. The second approach is the Backward-Algorithm, which is based on the method of infinite descent and a revision of Dahlquist's algorithm. Hence, there is a great deal of mathematics involved. The Backward-Algorithm will not guarantee that we find the smallest solution or all solutions when a solution does exist. The time complexity of the Forward-Algorithm and the Backward-Algorithm is also discussed. The Backward-Algorithm is strongly preferred from the point of time complexity.

Library of Congress Subject Headings

Mathematics -- Problems, exercises, etc

Format

application/pdf

Number of Pages

98

Publisher

South Dakota State University

Download

Share

COinS