--- title: "Factorise" id: 56293 type: "computer_media" slug: "factorise" url: "http://localhost/computer_media/factorise/" markdown_url: "http://localhost/computer_media/factorise.md" published_at: "2024-08-04T10:49:46+00:00" modified_at: "2026-03-30T21:42:41+00:00" author: "David Anderson" featured_image: url: "http://localhost/wp-content/uploads/2024/08/SCR-20240804-lfvw.png" excerpt: "A clever wheel-factorisation algorithm tackles numbers up to 4 billion, working around floating-point limitations with a custom large-number printer." category: - name: "Archived Media" slug: "archived-media" taxonomy: "category" url: "http://localhost/category/archived-media/" post_tag: - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "TS 2068" slug: "ts2068" taxonomy: "post_tag" url: "http://localhost/tag/ts2068/" model: - name: "Timex/Sinclair 2068" slug: "ts-2068" taxonomy: "model" url: "http://localhost/model/ts-2068/" genre: - name: "Mathematics" slug: "mathematics" taxonomy: "genre" url: "http://localhost/type/mathematics/" media_contents: - id: 56277 title: "Timex Sinclair Public Domain Library Tape 2001" type: "computer_media" url: "http://localhost/computer_media/timex-sinclair-public-domain-library-tape-2001/" media_type: "Program" download_url: "https://archive.org/download/timex-sinclair-software-archive/Factorise%20%28198x%29%28Thomson%2C%20W.%20E.%29%28TS2068%29%28UK%29%28Program%29.zip" mediadate: "198x" images: - url: "http://localhost/wp-content/uploads/2024/08/SCR-20240804-lfvw.png" media_type_tags: "Mathematics" --- # Factorise This program factorises integers up to 4,294,967,296 (2³²) by trial division, using a compact wheel-factorisation scheme stored in DATA statements. Rather than testing every integer as a divisor, it uses a precomputed sequence of 48 increments that skips multiples of 2, 3, 5, and 7, reducing the number of trial divisions significantly. A notable challenge addressed in the code is that the machine’s floating-point arithmetic cannot represent large integers exactly, so lines 300–320 implement a custom large-number printing routine that splits the number at 100,000 to avoid precision loss. The loop at line 130 uses a `RESTORE`/`NEXT B` trick to cycle through the wheel increments repeatedly without a conventional loop restart. *** ## Program Analysis ### Program Structure The program is organised into three logical sections: 1. **Initialisation (lines 20–60):** DATA tables are defined and the user inputs a number `N`. 2. **Factorisation loop (lines 70–130):** Trial division using a wheel increment sequence read from DATA. 3. **Output and large-number printing (lines 200–320):** Handles prime reporting and a subroutine for printing numbers that exceed floating-point integer precision. ### Wheel Factorisation The DATA at lines 20 and 30 encode a *wheel* — a sequence of 53 increments (starting from 2) that, when accumulated, generate candidate divisors coprime to 2, 3, 5, and 7. This avoids testing any multiple of those primes, giving roughly a 77% reduction in trial divisions compared to testing every integer. Line 20 seeds the first few small primes (2, 3, 5, 7, 11) and line 30 provides the 48-step repeating cycle of the wheel. The loop at lines 80–130 reads each increment `Z` from DATA, accumulates into `D`, and tests whether `D` divides `N` exactly. When the wheel is exhausted (after 53 steps, `B` runs 0 to 52), line 130 executes `RESTORE 30` to reset to the repeating part of the wheel, then sets `B=4` before `NEXT B` increments it to 5, effectively re-entering the FOR loop mid-cycle to continue with the 48-step repeat. This is a well-known BASIC trick for cycling through DATA without a full restart. ### Termination Condition The trial division stops early at line 100 when `Q = N/D` is less than `D`. At that point, any remaining factor of `N` must be prime (it cannot have two factors both greater than its square root), so the remaining `N` is printed directly by the subroutine at line 300. ### Large-Number Printing Subroutine (Lines 300–320) The ZX81/TS1000/Spectrum floating-point format holds only about 9–10 significant decimal digits, so numbers approaching 2³² ≈ 4.3 × 10⁹ can be printed in scientific notation rather than as exact integers. The subroutine at line 300 works around this: - `H = INT(N / 1e5)` extracts the high part (digits above 100,000). - If `H` is zero, the number fits in five digits and is printed directly. - Otherwise, `H` is printed, then `STR$(N - 1e5*(H-1))` produces a string of the form `"1XXXXX"` (always six characters starting with 1 due to the `H-1` offset), and `(2 TO )` slices off the leading `"1"`, yielding the zero-padded lower five digits. This is an elegant two-part decimal split that avoids any reliance on integer formatting and correctly zero-pads the lower segment. ### Output Formatting Line 110 uses the expression `PRINT "=" AND NOT F` to conditionally print the equals sign only before the first factor — when `F=0` (no factor found yet), `NOT F` is 1, so `"=" AND 1` yields `"="`; subsequently `NOT F` is 0 and the string evaluates to `""`. This avoids an explicit `IF` branch for the separator, keeping the line compact. ### Key Variables | Variable | Role | | --- | --- | | `N` | Current number being factorised (reduced as factors are found) | | `D` | Current trial divisor (accumulated from wheel increments) | | `Z` | Wheel increment read from DATA | | `B` | FOR loop counter (0–52) over the DATA entries | | `F` | Flag: 0 if no factor found yet, 1 after first factor | | `Q` | Quotient `N/D`, tested for integer value | | `H` | High part of `N` in the printing subroutine | ### Notable Anomalies The `RESTORE 30: LET B=4: NEXT B` at line 130 re-enters the `FOR B=0 TO 52` loop by manipulating the loop counter directly. This relies on the interpreter allowing `NEXT B` to continue a loop whose counter was set outside of it, which is standard behaviour. However, because `B` is set to 4 and then `NEXT B` increments it to 5, the loop will now run from 5 to 52 — consuming 48 iterations, matching the 48 entries in the DATA at line 30 exactly. The upper limit stated in the prompt (`<=4294967296`) is 2³², but the actual reliable limit is constrained by floating-point precision to numbers where all factors can be distinguished exactly — in practice the routine works correctly for inputs within the ~9-digit precision range of the floating-point system. ## Source Code ``` 1 REM "FACTORISE" 2 REM By W.E. Thomson 3 REM ZX Computing Monthly 20 DATA 2,1,2,2,4 30 DATA 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,6,4,10,2,10 40 RESTORE 20 50 INPUT "INPUT A NUMBER <=4294967296: ";N 60 GO SUB 300 70 LET F=0: LET D=0 80 FOR B=0 TO 52: READ Z: LET D=D+Z 100 LET Q=N/D: IF Q