The MASM Forum
General => The Soap Box => Topic started by: jj2007 on April 06, 2014, 05:47:54 PM
-
For the math guys here: Can you see a pattern?? This is Euler 20 (https://projecteuler.net/problem=20).
SWITCH uMsg
CASE WM_CREATE
Dim fact() As DWORD
push 0
fld1
Print Chr$("N", 9, "Sum", 9, "N", 33)
For_ ecx=0 To 19
inc stack
fimul stack
Let esi=Str$("%u", ST(0))
push esi
xor eax, eax
.While 1 ; get sum of digits
lodsb
sub al, "0"
.Break .if Sign?
add ah, al
.Endw
pop esi
movzx eax, ah
mov fact(ecx), eax
Print Str$("\n%i\t", ecx+1), Str$(fact(ecx)), Tb$, esi
Next
pop eax
CASE WM_PAINT
ArrayPlot hWnd, RgbCol(240, 255, 255) ; plot to hWin, background colour
ArrayPlot fact(), RgbCol(255, 0, 0), 5 ; array, dot colour, dot size
ArrayPlot exit, Chr$("Sum of digits in N", 33) ; finish with a title
-
Jochen,
For the math guys here: Can you see a pattern?? This is Euler 20 (https://projecteuler.net/problem=20).
no, can't see. Do you see a pattern? Nice program with another false positive by Avira. The challenge is to calculate the faculty of 100.
Gunther
-
you need some basic bignum functions, as 100! is 158 digits long :biggrin:
http://masm32.com/board/index.php?topic=222.0 (http://masm32.com/board/index.php?topic=222.0)
the Evr1 program has a large multiply function that should work
and - the LLKF9 routine can convert the binary result to a decimal string
-
i sat Euler on the back burner
i have 19 done (incl #20) - need 6 more to get the 25 award :P
-
Dave,
you need some basic bignum functions, as 100! is 158 digits long :biggrin:
that is the challenge. :lol:
Gunther
-
you need some basic bignum functions, as 100! is 158 digits long :biggrin:
Try this:
include \masm32\include\masm32rt.inc
.data?
Maxi=200
arr dd Maxi dup(?)
.code
start:
inc arr
y equ ecx
x equ ebx
v equ esi
i equ edi
m2m y, 2
.Repeat
xor v, v
xor i, i
.Repeat
mov eax, arr[4*i]
mul y
add eax, v
mov x, eax
xor v, v
.if x>9
mov eax, x
cdq
push 10
div dword ptr [esp]
mov v, eax
pop eax
mov arr[4*i], edx
.else
mov arr[4*i], x
.endif
inc i
.Until i>=Maxi
inc y
.Until y>100
sum equ esi
xor sum, sum
xor i, i
.Repeat
add sum, arr[4*i]
inc i
.Until i>=Maxi
print "Sum="
print str$(sum)
exit
end start
Credits to Daniel Scocco (http://www.programminglogic.com/solution-to-problem-20-on-project-euler/) :t
-
Jochen - don't google it !!!!!
that takes all the fun out of it - lol
the challenge is to come up with your own method :t
-
Dave,
Unfortunately I've neither the time (or the patience) nor the mathematical gifts for this kind of challenge. Still, I'd like to understand why it works ::)
-
:P
-
Hmm.... Interesting subject...
I have another approach but its written in C. Hope you guys don't mind it...
#include <stdio.h>
int main()
{
char buffer[500] = {0};
// init condition
int Val = 100;
buffer[0] = Val - (Val-1);
int len = 1;
int temp;
int i = 2;
int x;
int sum = 0;
// in case it'll accept as param
if (Val >= i)
{
for ( ; i <= Val; i++)
{
x = 0;
for (int u = 0; u < len; u++)
{
temp = buffer[u];
temp = (temp * (Val - (Val - i))) + x;
if (temp >= 10)
{
buffer[u] = temp % 10;
x = temp / 10;
if (u+1 > len-1)
{
len++;
}
}
else
{
buffer[u] = temp;
x = 0;
}
}
}
}
for (int i=0; i<len;i++)
{
sum +=buffer[i];
}
printf("%d", sum);
return 0;
}it will store the result in char buffer in backward. for example 24 will be stored as 4, 2.
few more possibilities: the buffer can be dynamically allocated, and it can be set as a function which accept the number of digit sum as parameter (for example 100 or maybe 200 etc).
edit: corrected some typo...
-
I have another approach
So how does it differ from Scocco's solution (http://www.programminglogic.com/solution-to-problem-20-on-project-euler/) posted above?
-
...
Still, I'd like to understand why it works ::)
I'm eager to understand its working (IMO based on some sophisticated math formula) too.
Could anyone of math lovers to shed some light on this subject?
-
So how does it differ from Scocco's solution (http://www.programminglogic.com/solution-to-problem-20-on-project-euler/) posted above?
it differ in the way it perform calculation and whats being stored in the buffer.. mine stores the calculated result backwards... and it just perform simple elementary multiplication... really I'm also surprised it works.... because I don't really into math... I just love the logic behind it...
if you want another result can modify memory size and ival...
I have been tried it with 1500! and higher number. as long as the buffer is sufficient enough it works.. but of course it will took more times....
the buffer can be dump to sdtout, to see the calculation result... but it's in backward state.... also the lenght of the result...
-
well - i do see a pattern in the original post
and, it may be part of the basis for the Daniel Scocco code
because the initial problem asks for the sum of digits, there is a shortcut
as you work from 1, up to N, you pass multiples of 5
because there is also an associated multiple of 2, an additional trailing 0 is generated
multiplier number of trailing 0's
1-4 0
5-9 1
10-14 2
15-19 3and so on
for this specific problem, that means you can divide the result by 10 each time a new trailing zero is generated
(0's will not affect the digit total)
this allows you to keep a smaller running accumulator value :t
in fact, rather than multiplying by the 5-multiple, multiply by the 5-multiple/10
similar shortcuts are common in many of the Euler Project problems :biggrin:
-
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
the result has 24 trailing 0's that don't need to be tallied
-
it differ in the way it perform calculation and whats being stored in the buffer
IMHO you can sue Scocco for plagiarism. Replace in Scocco's solution:
- vet with buffer
- x with temp
- v with x
- i with u
- >9 with >=10
Scocco:
temp = buffer[ u ]*y + x;
x = 0;
if (temp > 9) {
f = temp % 10;
x = temp / 10;
}
else
f = temp;
buffer[ u ] = f;
Dubby:
temp = buffer[ u ];
temp = (temp * (Val - (Val - i))) + x;
if (temp >= 10)
{
buffer[ u ] = temp % 10;
x = temp / 10;
}
else
{
buffer[ u ] = temp;
x = 0;
}
-
whoaa I didn't even notice it.... to be honest... I didn't even understand how's Scocco solution works.... why it needs 500 loops....
really while come up with the approach I didn't even look at another codes...
-
... I didn't even understand how's Scocco solution works....
So maybe you explain us how your code works
-
...
-
OK I'll explain my logic behind it... I'm not stealing another person's code.. why would I do that?? I'm not that kind of person...!!! :eusa_naughty:
let's take 10! for example
10-1 = 9 10-(10-1) = 1 1
10-2 = 8 10-(10-2) = 2 2
10-3 = 7 10-(10-3) = 3 6
10-4 = 6 10-(10-4) = 4 24
10-5 = 5 10-(10-5) = 5 120
10-6 = 4 10-(10-6) = 6 720
10-7 = 3 10-(10-7) = 7 5040
10-8 = 2 10-(10-8) = 8 40320
10-9 = 1 10-(10-9) = 9 362880
Ok so it's like this first the buffer[0] is init with 1
from iteration 1 up to 3 (1 based) only need single char buffer... take it from buffer multiply it and put it back...
but then here comes 24 which is 6*4... so I mod it with 10 to grab the 4 and put it in buffer[0]... and we have 2.. right..? so I need to increase the len (the second loop) to put it insidide buffer[1]
right now the buffer contain
42
then multiply it by 5..
take the 4 from the buffer multiply it by 5 the result is 20... put zero in back to buffer[0] and keep the 2,, then take the 2 from buffer[1] multiply it by 5 we have 10 now I need to store 0 to buffer[1] and 1 buffer[2] but remember that we keep 2 from 4*5 this 2 need to go down into buffer[1] so buffer[1] = 2 + 0.
right now the buffer contain
021
then multiply it by 6
6*0 = 0 --> buffer[0]
6*2 = 12 ==> 2 --> buffer[1]; and 1 --> buffer[2]
6*1 = 6 --> buffer[2]
so...
buffer[0] = 0;
buffer[1] = 2;
buffer[2] = 1 + 6;
so the buffer become
027
multiply it by 7
7*0 = 0 --> buffer[0]
7*2 = 14 ==> 4 --> buffer[1]; 1 --> buffer[2]
7*7 = 49 ==> 9 --> buffer[2]; 4 --> buffer[3]
so...
buffer[0] = 0;
buffer[1] = 4;
buffer[2] = 1 + 9;
buffer[3] = 4;
but since the buffer[3] is 10 then it become
buffer[0] = 0;
buffer[1] = 4;
buffer[2] = 0;
buffer[3] = 5;
the buffer:
0405
see the pattern...
then loop through the buffer to sum it up....
You can verify them under the debugger...
-
Hi Dubby,
OK I'll explain my logic behind it... I'm not stealing another person's code.. why would I do that?? I'm not that kind of person...!!! :eusa_naughty:
be relaxed. Nobody would say you're a code thief. Sometimes lead similar algorithms to similar code.
By the way, your explanation is good and comprehensible. :t Well done.
Gunther
-
Dubby, thank you for explanation . Now it makes sense ... more or less
-
this might prove interesting
http://oeis.org/A004152 (http://oeis.org/A004152)
-
Dave,
http://oeis.org/A004152 (http://oeis.org/A004152)
yes indeed, a good source. Interesting enough:
founded in 1964 by N.J.A. Sloan (https://en.wikipedia.org/wiki/Neil_Sloane)
Gunther
-
Dubby's algo is more or less as you would do it using paper and pencil. It can be translated to assembly using BCD's. The necessary array length can be defined in advance by using Windows calculator to find the number of digits that would eventually be produced.
Don't even think about using such a procedure to solve Problem 160! :shock:
-
Hi Raymond,
I'm glad to see you again after a little while.
Don't even think about using such a procedure to solve Problem 160! :shock:
That's right.
Gunther
-
For the math guys here: Can you see a pattern??
A quick squiz gives me this
Y(n+1) = Y(n) *(n+1) ...................for n = {1, inf}
n!, I suppose
:-)
-
What do you see to the right of "Sum" in the blue area of the picture in the first post?
-
The Sum is always even except for N=1, therefore never Prime (except for 1 and 2 ;) )
The number of Sum digits <= N
The number of Sum digits seems to be a linear function of N.
:biggrin: