Index - System Notes

The Problem

Find all 3×3 Matrices whose determinant is equal to one, and after squaring all terms the determinant is also one. (Zeros are not allowed as terms).

There are seven known solutions with terms between +1 and +20, with no apparent pattern. (There are six more as of 02/02/94, and some more in the same month).

Partial Solution

Since there is no way of testing for patterns, I used a nested FOR loop nine levels deep. The main problem is that on a PC it would take about a million years to execute with only 9^100 (9 to the 100th power) possibilities, and execution time is increased dramatically as more terms are added to be tested.

Finding Spare Time

The next problem was to get the PC to even run the program enough hours to get closer to a solution. The most logical route, I thought was to make a screen saver that would execute the math problem in the background. While execution is slowed considerably by writing graphics to the screen, it is more practical than a screen blanker for two reasons. 1) The user knows that a program is active, and that there is no problem with the monitor, and 2) Screen savers are more likely to be used than screen blankers, because of their aesthetic value.

Getting Closer

Not having access to a mainframe that can dedicate all its spare time to solving my problem, I decided to separate the problem over a number of PC’s (I installed it on 40 IBM PC’s – 386DX/33).

Now instead of a million years, it would only take 250,000 years.

Increasing Speed

Writing the program in C gives about ten times the execution speed. The problem can then be solved in only 25,000 years. I have chosen the for loop, because it is the fastest way of testing consecutive numbers. Using integers rather than floating point (real numbers) increases program execution, and with some compilers, using “I++” is faster than using “I = I + 1”. As I continue experimenting with optimization techniques, any other language or algorithm optimization tips would be appreciated. I have just recently (02/94) discovered that some patterns of numbers may be skipped entirely (e.g. -10 -9 -8 -4 -3 -3 -5 -7 -5 as terms gives the same determinant as -10-9 -8 4 3 3 5 7 5, because the terms that are multiplied can be both positive or both negative resulting in a positive number for those operations). I’m sure there is an algorithm that can be written to skip redundant values.

Spreading Out

In order to spread out the problem over more PC’s, I have offered this freeware version of MATRIX, which will use a different starting number for the terms to be tested. This is your serial number which will tell me which numbers are being tested. The program is free to use, but registration is important, and source code may be purchased. Now with 1000 copies running, it should only take 25 years to test all possible solutions from -100 to +100. With the increasing speed of PC’s, the problem can probably be solved in less than five years. Or, if 25,000 copies would run for one year, we would have all the solutions tested.

Registration

Registration is free. (Any contributions of $5.00 or $10.00 would be appreciated, and would add your name to the mailing list to recieve update information, and information about solutions that are found). You may use the registration form in the file register.txt to be assigned a starting number, and range of values to check. You may select a temporary number while the registration is being processed, but there is no guarantee that someone else is not already using the same numbers. The registration number will be a series of 11 digits. The first nine are the terms of the matrix, and the last two are the min/max values. The values are selected based on the machine you plan to run the program on. An XT will have a range close to 20 or 30, and a 486 or Pentium will have a range closer to 200. For faster machines you may start with the values in the log file, and change only the first or second digits (these are changed least frequently, like an odometer). So your temporary value might be -90, -99, -99, -99, -99, -99, -99, -99, -99, -99, 99.

Files:

Program may be distributed freely as long as all files are included, and the program is not used for profit (except with express written permission of the publisher).

MAT BAT 185 3-03-94 11:31a Run program MATRIX COM 18422 1-07-94 9:45p Program File ANS BAT 307 3-03-94 11:33a Reads answer.log MATRIX LOG 34 3-03-94 10:59a Current values ANSWER LOG varies Created if answers are found MATRIX DOC 5191 3-03-94 12:21p This file REGISTER TXT 1477 3-03-94 12:15p Registration form

Comments:

Please send any comments, suggestions, critiques, & registrations to:

ScottM systemnotesorg AT yahoo DOT com

matrix.c Source Code

matrix zip file

downloads

Help for Aspiring Sysadmins

Linux / Open Source / Howto / Tips & Tricks

Latest News

Links:

Do you find this site useful?