Babbage problem: Difference between revisions
Content deleted Content added
Cyril Nocton (talk | contribs) →⍣ operator: Minor change. |
Added PascalABC.NET |
||
(47 intermediate revisions by 19 users not shown) | |||
Line 69:
<pre>
Solution is: i= 25264 (i*i= 638269696)
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program babbage64.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result = "
szMessStart: .asciz "Program 64 bits start.\n"
szCarriageReturn: .asciz "\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24 // conversion buffer
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrszMessStart
bl affichageMess
ldr x4,qNbStart // start number = 269696
mov x5,#0 // counter multiply
ldr x2,qNbMult // value multiply = 1 000 000
mov x6,x4
1:
mov x0,x6
bl squareRoot // compute square root
mul x1,x0,x0 // compute square
umulh x3,x0,x0
cmp x3,#0 // overflow ?
bne 100f // yes -> end
cmp x1,x6 // perfect square
bne 2f // no -> loop
ldr x1,qAdrsZoneConv
bl conversion10
mov x0,#3 // string number to display
ldr x1,qAdrszMessResult
ldr x2,qAdrsZoneConv // insert conversion in message
ldr x3,qAdrszCarriageReturn
bl displayStrings // display message
b 100f // end
2:
add x5,x5,#1 // increment counter
mul x3,x5,x2 // multiply by 1 000 000
add x6,x3,x4 // add start number
b 1b
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qNbStart: .quad 269696
qNbMult: .quad 1000000
qAdrsZoneConv: .quad sZoneConv
qAdrszMessResult: .quad szMessResult
qAdrszMessStart: .quad szMessStart
/***************************************************/
/* Compute integer square root by Héron méthode */
/***************************************************/
/* r0 number */
/* r0 return root */
squareRoot:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
cmp x0,#0 //
beq 100f
cmp x0,#4 // if < 4 return 1
mov x1,1
csel x0,x1,x0,lo
blo 100f
lsr x1,x0,#1 // division by 2 -> divisor
1:
mov x3,x1 // save previous result
udiv x2,x0,x1 // divide number by previous result
add x1,x1,x2 // add quotient to previous result
lsr x1,x1,#1 // division by 2
cmp x1,x3 // compare result and previous result
blo 1b // loop if result is smaller then previous result
mov x0,x3 // else return previous result
100:
ldp x2,x3,[sp],16 // restaur registres
ldp x1,lr,[sp],16 // restaur registres
ret
/***************************************************/
/* display multi strings */
/* new version 24/05/2023 */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* x4 address string4 */
/* x5 address string5 */
/* x6 address string5 */
/* x7 address string6 */
displayStrings: // INFO: displayStrings
stp x8,lr,[sp,-16]! // save registers
stp x2,fp,[sp,-16]! // save registers
add fp,sp,#32 // save paraméters address (4 registers saved * 8 bytes)
mov x8,x0 // save strings number
cmp x8,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x8,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x8,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x8,#3
ble 100f
mov x0,x4
bl affichageMess
cmp x8,#4
ble 100f
mov x0,x5
bl affichageMess
cmp x8,#5
ble 100f
mov x0,x6
bl affichageMess
cmp x8,#6
ble 100f
mov x0,x7
bl affichageMess
100:
ldp x2,fp,[sp],16 // restaur registers
ldp x8,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 64 bits start.
Result = 25264
</pre>
Line 176 ⟶ 339:
+25264 when squared is: +638269696
</pre>
=={{header|Amazing Hopper}}==
<syntaxhighlight lang="c">
#include <basico.h>
algoritmo
decimales '0'
número = 0, i=10
ciclo:
iterar grupo( número+=2, \
#( (número^2) % 1000000 != 269696 ), ; )
imprimir ("The smallest number whose square ends in 269696 is: ",\
número,\
"\nIt's square is: ", #(número ^ 2), NL )
i--, jnz(ciclo)
terminar
</syntaxhighlight>
{{out}}
<pre>
The smallest number whose square ends in 269696 is: 25264
It's square is: 638269696
The smallest number whose square ends in 269696 is: 99736
It's square is: 9947269696
The smallest number whose square ends in 269696 is: 150264
It's square is: 22579269696
The smallest number whose square ends in 269696 is: 224736
It's square is: 50506269696
The smallest number whose square ends in 269696 is: 275264
It's square is: 75770269696
The smallest number whose square ends in 269696 is: 349736
It's square is: 122315269696
The smallest number whose square ends in 269696 is: 400264
It's square is: 160211269696
The smallest number whose square ends in 269696 is: 474736
It's square is: 225374269696
The smallest number whose square ends in 269696 is: 525264
It's square is: 275902269696
The smallest number whose square ends in 269696 is: 599736
It's square is: 359683269696
The smallest number whose square ends in 269696 is: 650264
It's square is: 422843269696
</pre>
<p>Comentarios "in spanish":</p>
<p>
Documentación:</p>
<p>Establece que se trabajará con números sin decimales:</p>
"decimales(0)" (A)
La variable que tendrá el número cuyo cuadrado finaliza
con los dígitos 269696. Se inicializa con valor 0:
"número" (B)
La variable que controlará 11 iteraciones del proceso
principal. Se inicializa con 10, y se decrementará hasta
llegar a 0, de acuerdo a lo descrito en 1.4, 1.5 y 1.6:
"i" (C)
Esto permitirá encontrar 11 números que cumplan con lo
buscado.
-------------------------------------------------------------
Establece una etiqueta de salto, donde la ejecución del
programa saltará si se cumple una condición, que será
explicada en 1.4 y 1.5:
"CICLO:" (1.1)
Una macro que iterará el proceso principal donde por cada
incremento de "número" evaluará si los últimos dígitos del
cuadrado de "número" son los dígitos buscados por el señor
Babbage:
"iterar grupo" (1.2)
Explicación del proceso descrito en 1.2:
número+=2 (1.2.1) : incrementará el valor de la
variable "número" de 2 en 2.
número^2 (1.2.2) : cuadrado de "número".
% : resto módulo, resto de la división.
1000000 : esto permite obtener el resto de la
división de tamaño 6 dígitos.
Si el resultado de "(número^2)%1000000" es igual a
269696, entonces, "número" es el número buscado.
Una macro que dispondrá los mensajes y los resultados de
1.2.1 y 1.2.2, los que serán mostrados en pantalla:
"IMPRIMIR" (1.3)
Dispone el valor de la variable "i" para ser evaluada por
"JNZ", y luego la decrementará en 1:
"i--" (1.4)
Evalúa: si la variable no es cero, entonces saltará a la
posición del programa señalada en 1.1;
"JNZ(CICLO)" (1.5)
de lo contrario, si "i" es cero, entonces continuará con
el resto del programa, que será "terminar" la ejecución del
algoritmo:
"TERMINAR" (1.6)
Comentarios:
JNZ : significa Jump if Non-Zero.
#() : macro que permite resolver expresiones infijas en
tiempo de compilación.
</p>
=={{header|APL}}==
===⍳
If at all possible, I would sit down at a terminal <i>with</i> Babbage and invite him to experiment with the various functions used in the program.
<syntaxhighlight lang="apl"> ⍝ We know that 99,736 is a valid answer, so we only need to test the positive integers from 1 up to there:
Line 192 ⟶ 477:
{{out}}
<pre>25264</pre>
===⍣
<syntaxhighlight lang=apl
⍝ s = 520 + 2 ... + 2 ⍣ <= power
⍝ s × s = n × 1000000 + 269696 | <= remainder
2+⍣{269696=1000000|⍺×⍺}520
</syntaxhighlight>
{{out}}
<
25264
</pre>
====Documentation====
<pre>
Answer: n
△
│
Yes│
│
┌── remainder = 269696 ? ──┤
│ │
│ Power No│
│ (⍣) │
│ ▽
n ← n + 2 ◁─────────────────── n ← 520
Flow Created with Monodraw
</pre>
=={{header|AppleScript}}==
Line 591 ⟶ 900:
<pre>25264</pre>
=={{header|Asymptote}}==
<syntaxhighlight lang="Asymptote">int n = 519;
while (269696 != (n^2) % 1000000) {
++n;
}
write("The smallest number whose square ends in 269696 is: ", n);
write("It's square is ", n*n);</syntaxhighlight>
{{out}}
<pre>The smallest number whose square ends in 269696 is 25264
Its square is 638269696</pre>
=={{header|AutoHotkey}}==
Line 747 ⟶ 1,069:
{{out}}
Identical to the first BBC BASIC version.
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|BASIC256}}
<syntaxhighlight lang="qbasic">10 cls
20 number = 2
30 while ((number^2) mod 1000000) <> 269696
40 number = number+2
50 wend
60 print "The smallest number whose square ends in 269696 is: " number
70 print "It's square is " number*number
80 end</syntaxhighlight>
==={{header|GW-BASIC}}===
{{works with|MSX_BASIC}}
{{works with|PC-BASIC|any}}
{{trans|Applesoft BASIC}}
<syntaxhighlight lang="qbasic">10 CLS
20 DEF FN ST(A#) = N# - INT (A#) * INT (A#)
30 N# = 269696!
40 N# = N# + 1000000!
50 R# = SQR(N#)
60 IF FN ST(R#) <> 0 AND N# < 999999999# THEN GOTO 40
70 IF N# > 999999999# THEN GOTO 110
80 PRINT "The smallest number whose square ends in 269696 is:";R#
90 PRINT "It's square is:";N#
100 END
110 PRINT "There is no solution for values smaller than 999999999."</syntaxhighlight>
{{out}}
<pre>The smallest number whose square ends in 269696 is: 25264
It's square is: 638269696</pre>
==={{header|MSX Basic}}===
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|QBasic}}===
Line 811 ⟶ 1,167:
160 PRINT "The smallest number whose square ends in 269696 is:";R
170 PRINT "It's square is";N</syntaxhighlight>
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Babbage problem"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
number = 524
DO
number = number + 2
LOOP UNTIL ((number ** 2) MOD 1000000) = 269696
PRINT "The smallest number whose square ends in 269696 is: "; number
PRINT "It's square is "; number ** 2
PRINT "It's square is "; number * number
END FUNCTION
END PROGRAM</syntaxhighlight>
=={{header|Batch File}}==
Line 1,031 ⟶ 1,405:
=={{header|COBOL}}==
<syntaxhighlight lang="
PROGRAM-ID. BABBAGE-PROGRAM.
* A line beginning with an asterisk is an explanatory note.
* The machine will disregard any such line.
DATA DIVISION.
WORKING-STORAGE SECTION.
* In this part of the program we reserve the storage space we shall
* be using for our variables, using a 'PICTURE' clause to specify
Line 1,042 ⟶ 1,417:
* The prefixed number 77 indicates that these variables do not form part
* of any larger 'record' that we might want to deal with as a whole.
77 N PICTURE 99999.
* We know that 99,736 is a valid answer.
77 N-SQUARED PICTURE 9999999999.
77 LAST-SIX PICTURE 999999.
PROCEDURE DIVISION.
* Here we specify the calculations that the machine is to carry out.
CONTROL-PARAGRAPH.
PERFORM COMPUTATION-PARAGRAPH VARYING N FROM 1 BY 1
UNTIL LAST-SIX IS EQUAL TO 269696.
STOP RUN.
COMPUTATION-PARAGRAPH.
MULTIPLY N BY N GIVING N-SQUARED.
MOVE N-SQUARED TO LAST-SIX.
* Since the variable LAST-SIX can hold a maximum of six digits,
* only the final six digits of N-SQUARED will be moved into it:
* the rest will not fit and will simply be discarded.
IF LAST-SIX IS EQUAL TO 269696 THEN DISPLAY N.
END PROGRAM BABBAGE-PROGRAM.</syntaxhighlight>
{{out}}
<pre>25264</pre>
Line 1,127 ⟶ 1,505:
The smallest number whose square ends in 269696 is: 25264
Its square is: 638269696</pre>
=={{header|Component Pascal}}==
Line 1,223 ⟶ 1,539:
let n = n + 2
wait
loopuntil (
print "
print "
{{out| Output}}<pre>calculating...
The smallest number whose square ends in 269696 is: 25264
It's square is 638269696</pre>
=={{header|D}}==
Line 1,474 ⟶ 1,790:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'math;
Line 1,482 ⟶ 1,798:
var n := 1;
until(n.sqr().mod
{
n += 1
Line 1,506 ⟶ 1,822:
|> IO.puts</syntaxhighlight>
{{out}}
<pre>
25264
</pre>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
^|
| Since the number must end with 269696 we can safely start counting from its square root;
| we are only interested in its integer part.
| We assign a value to a variable with "←".
| The modulo symbol for getting the remainder of a division is "%".
|^
int i ← int!√269696
while i² % 1000000 ≠ 269696 do ++i end
writeLine(i)
</syntaxhighlight>
{{out}}
<pre>
Line 1,837 ⟶ 2,170:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Babbage_problem}}
'''Solution'''
[[File:Fōrmulæ - Babbage problem 01.png]]
[[File:Fōrmulæ - Babbage problem 02.png]]
=={{header|Gambas}}==
Line 2,347 ⟶ 2,682:
<syntaxhighlight lang="julia">
"""
babbage(x::Integer)
Returns the smallest positive integer whose square ends in `x`
"""
function babbage(x::Integer)
i = big(0) # start with 0 and increase by 1 until target reaached
d = 10^ndigits(x) # smallest power of 10 greater than x
while (i
i += 1 # try next squre of numbers 0, 1, 2, ...
end
return i
end
</syntaxhighlight>
Line 2,396 ⟶ 2,737:
...
</syntaxhighlight>
=={{header|langur}}==
<syntaxhighlight lang="langur">
for i = 2; i < 100000 ; i += 2 {
if i*i rem 1000000 == 269696 {
writeln "{{i}} ^ 2 == {{i^2}}"
break
}
}
</syntaxhighlight>
{{out}}
<pre>25264 ^ 2 == 638269696</pre>
=={{header|Liberty BASIC}}==
Line 2,474 ⟶ 2,828:
{{out}}
<pre>{{x->25264},{x->99736}}</pre>
=={{header|MATLAB}}==
<syntaxhighlight lang="MATLAB">
clear all;close all;clc;
BabbageProblem();
function BabbageProblem
% Initialize x to 524, as the square root of 269696 is approximately 519.something
x = 524;
% Loop until the square of x modulo 1000000 equals 269696
while mod(x^2, 1000000) ~= 269696
% If the last digit of x is 4, increment x by 2
% Otherwise, increment x by 8
if mod(x, 10) == 4
x = x + 2;
else
x = x + 8;
end
end
% Display the result
fprintf('The smallest positive integer whose square ends in 269696 = %d\n', x);
end
</syntaxhighlight>
{{out}}
<pre>
The smallest positive integer whose square ends in 269696 = 25264
</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Function that returns a list of digits given a nonnegative integer */
decompose(num) := block([digits, remainder],
digits: [],
while num > 0 do
(remainder: mod(num, 10),
digits: cons(remainder, digits),
num: floor(num/10)),
digits
)$
/* Test case */
block(babbage_param:269696,i:isqrt(babbage_param)+1,cache_babbage:decompose(babbage_param),
while rest(decompose(i^2),(length(decompose(i^2))-6))#cache_babbage do i:i+2,
i);
</syntaxhighlight>
{{out}}
<pre>
25264
</pre>
=={{header|MAXScript}}==
Line 2,726 ⟶ 3,132:
{{out}}
<pre>25264</pre>
=={{header|PascalABC.NET}}==
See [[#Pascal|Pascal]].
=={{header|Perl}}==
Line 3,086 ⟶ 3,495:
{{out}}
<pre>
lowest number is 25264 which squared becomes 638269696
true.
</pre>
===alternative===
with swi-prolog buildin between -> Output is the same
<syntaxhighlight lang="prolog">
babbage :-
Start is ceil(sqrt(269696)),
between(Start, inf, N),
Square is N * N,
Square mod 100 =:= 96, % speed up
Square mod 1000000 =:= 269696,!, % break after first true
format('lowest number is ~d which squared becomes ~d~n', [N, Square]).
</syntaxhighlight>
=={{header|PureBasic}}==
Line 3,410 ⟶ 3,830:
This could certainly be written more concisely. Extra verbiage is included to make the process more clear.
<syntaxhighlight lang="raku" line># For all
for 1 .. Inf -> $integer {
Line 3,429 ⟶ 3,849:
{{out}}
<pre>25264</pre>
Notice that `exit` ends the process itself instead of ending just the loop, as `last` would. `exit` would arguably be easier to understand for Babbage though, so it may better fill the task requirement.
=={{header|Red}}==
Line 3,694 ⟶ 4,116:
Which outputs the same thing as above.
=={{header|S-BASIC}}==
Because we have to use double-precision floating point to represent the required number of digits, and because the approach to calculating a double-precision n mod 1000000 to isolate the right-most six digits of the square is particularly inefficient, the program will take a long time to find the solution (but it will, eventually!)
<syntaxhighlight lang="BASIC">
$lines
$constant true = FFFFH
$constant false = 0
var n, sq, r = real.double
var done = integer
print "Finding smallest number whose square ends in 269696"
n = 520 rem - no smaller number has a square that large
done = false
rem - no need to search beyond the number Babbage already knew
while not done and n <= 99736.0 do
begin
sq = n * n
rem - compute sq mod 1000000 by repeated subtraction
r = sq
while r >= 1000000.0 do
r = r - 1000000.0
if r = 269696.0 then
begin
print using "The smallest number is ######"; n
print using "and its square is ##,###,###,###"; sq
done = true
end
rem - only even numbers can have a square ending in 6
n = n + 2
end
end
</syntaxhighlight>
{{out}}
<pre>
Finding smallest number whose square ends in 269696
The smallest number is 25264
and its square is 638,269,696
</pre>
=={{header|Scala}}==
Line 4,204 ⟶ 4,669:
638269696
</pre>
=={{header|Transd}}==
Line 4,448 ⟶ 4,912:
<pre>The smallest positive integer whose square ends in 269696 is 25264.
Its square is 638269696.</pre>
=={{header|Vedit macro language}}==
<syntaxhighlight lang="vedit">
// Vedit Macro Language stores numerical values in numeric registers,
// referred as #0 to #255.
// Check all positive integer values until the required value found
for (#1 = 1; #1 < MAXNUM; #1++) {
#2 = #1 * #1 // #2 = square of the value
// The operator % is the modulo operator (the remainder of division).
// Modulo 1000000 gives the last 6 digits of a value.
#3 = #2 % 1000000
if (#3 == 269696) {
break // We found it, lets stop here
}
}
if (#1 < MAXNUM) {
Message("The smallest number whose square ends in 269696 is ", NOCR)
Num_Type(#1)
Message("The square is ", NOCR)
Num_Type(#2)
} else {
Message("Condition not satisfied before MAXNUM reached.)
}
</syntaxhighlight>
{{Out}}
<pre>The smallest number whose square ends in 269696 is 25264
The square is 638269696</pre>
=={{header|Verilog}}==
<syntaxhighlight lang="Verilog">module main;
real n;
initial begin
while (((n**2) % 1000000) != 269696) n=n+2;
$display("The smallest number whose square ends in 269696 is ", n);
$display("It's square is ", n*n);
end
endmodule</syntaxhighlight>
=={{header|Visual Basic .NET}}==
Line 4,506 ⟶ 5,013:
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
The answer must be an even number and it can't be less than the square root of 269,696.
So, if we start from that, keep on adding 2 and squaring it we'll eventually find the answer.
Line 4,512 ⟶ 5,019:
*/
import "./fmt" for Fmt // this enables us to format numbers with thousand separators
var start = 269696.sqrt.ceil // get the next integer higher than (or equal to) the square root
start = (start/2).ceil * 2 // if it's odd, use the next even integer
|