Sorry, Sliver - I tried to merge the threads and the other is gone?
It must have went somewhere? I'll try to find it...
Anyway, my comments were that you assume the houses start
numbering at 1 - this limits the possible output of your algo.
You can compress the loop code with the algo for sum of a series
of integers equation.
It must have went somewhere? I'll try to find it...
Anyway, my comments were that you assume the houses start
numbering at 1 - this limits the possible output of your algo.
You can compress the loop code with the algo for sum of a series
of integers equation.
Did they assume that also?
I got the same output that they did...
A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back
It said the that "woman" walked to the left of her house (to the end of the block) and then the next time walked to the right of her house to the end of the block...
This would assume from here house (k)
(k-1) + (k-2) + (k-3)+ ... + 2 + 1 = (k+1) + (k+2)+ ... (k+n)
where k is a positive integer
Sliver
Not sure where to post this code... didn't understand what you meant by merge the threads
I got the same output that they did...
A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back
It said the that "woman" walked to the left of her house (to the end of the block) and then the next time walked to the right of her house to the end of the block...
This would assume from here house (k)
(k-1) + (k-2) + (k-3)+ ... + 2 + 1 = (k+1) + (k+2)+ ... (k+n)
where k is a positive integer
Sliver
Not sure where to post this code... didn't understand what you meant by merge the threads
; #########################################################################
.386
.model flat, stdcall
option casemap :none ; case sensitive
; #########################################################################
include \masm32\include\windows.inc
include \masm32\include\user32.inc
include \masm32\include\kernel32.inc
include \masm32\include\masm32.inc
include \masm32\include\debug.inc
includelib \masm32\lib\user32.lib
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\masm32.lib
includelib \masm32\lib\debug.lib
Main PROTO
; #########################################################################
.data
; #########################################################################
.code
start:
invoke Main
invoke ExitProcess,0
; #########################################################################
Main proc
LOCAL OurHouse:DWORD
LOCAL PrevHouseSum:DWORD
mov ecx, 0
StartSearch:
push ecx
xor eax, eax
xor edx, edx
.while (edx < ecx)
add eax, edx
inc edx
.endw
mov PrevHouseSum, eax
mov OurHouse, ecx
xor edx, edx
inc ecx
.while (edx < eax)
add edx, ecx
.if (PrevHouseSum == edx)
PrintText "Our House:"
PrintDec OurHouse
PrintText "The Last House of the street:"
PrintDec ecx
PrintText " "
.endif
inc ecx
.endw
pop ecx
inc ecx
cmp ecx, 10000000
jne StartSearch
ret
Main endp
; #########################################################################
end startI was trying to change the name of the thread to eliminate confusion with problem 100. Looks like the other one is gone - the board said it merged the threads - won't be trying that again without some testing first!
Looks like I skiped right over the from 1. You are correct.
Problem 138 :: Street Numbers
Looks like I skiped right over the from 1. You are correct.
Problem 138 :: Street Numbers
Took about 30 minutes to check up to 1.2 million...
I think I'll do some serious optimization and see if i can take that down to 2 minutes :-)
I think I'll do some serious optimization and see if i can take that down to 2 minutes :-)
The equation you need to solve for integers is:
2(b^2 + 2b + 1) = c^2 + c
House # = b+1
Last # = c
Edit: That isn't correct - I made an error somewhere in my math...
Edit: Okay, it is correct - I made an error in my error. :tongue:
Or, more simply put:
2 b^2 = c^2 + c
House # = b
Last # = c
My algorithm isn't working so good because of b^2 overflowing 32 bits, and 64 bit math is slower. I have everything happening in registers and still taking too long...
How could the times they list be correct? Some even say they are using the same formula as I am, and with a time of zero?
2(b^2 + 2b + 1) = c^2 + c
House # = b+1
Last # = c
Edit: That isn't correct - I made an error somewhere in my math...
Edit: Okay, it is correct - I made an error in my error. :tongue:
Or, more simply put:
2 b^2 = c^2 + c
House # = b
Last # = c
My algorithm isn't working so good because of b^2 overflowing 32 bits, and 64 bit math is slower. I have everything happening in registers and still taking too long...
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121How could the times they list be correct? Some even say they are using the same formula as I am, and with a time of zero?
This takes about half a minute on my machine. ;)
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161
ACM_138 MACRO
LOCAL MainLoop,iLoop,ACM_Template
sub esp,4
mov edi,1 ; initial house number
and DWORD PTR [esp],0 ; output counter
MainLoop:
inc edi
mov eax,edi ; b
mul eax ; b^2
add eax,eax
adc edx,edx
; guess at a good c ;)
push edx
push eax
fild QWORD PTR [esp]
fsqrt
fistp QWORD PTR [esp]
mov ecx,edx
mov esi,eax
pop ebx
add esp,4
dec ebx
iLoop:
mov eax,ebx
inc ebx
mul ebx ; c^2 + c = c (c + 1)
cmp edx,ecx
js iLoop
jne MainLoop
cmp eax,esi
js iLoop
jne MainLoop
;; Output will consist of 10 lines each containing a pair of numbers,
;; each printed right justified in a field of width 10.
_CONST SEGMENT
ACM_Template db "%10.ld%10.ld",0
_CONST ENDS
dec ebx
inc DWORD PTR [esp] ; line counter
invoke wsprintf,OFFSET ACM_Buff,OFFSET ACM_Template,edi,ebx
invoke DebugPrint,OFFSET ACM_Buff
cmp DWORD PTR [esp],10
jne MainLoop
pop eax
ENDMI had a few answers in between....
If you run my program for about 10 minutes you get a value at about 120,000 and 140,000
Sliver
---EDIT---
Doh...
Next Time I'm gonna make sure my program works before I post it :)
If you run my program for about 10 minutes you get a value at about 120,000 and 140,000
Sliver
---EDIT---
Doh...
Next Time I'm gonna make sure my program works before I post it :)
Thanks, I'll give it a try. Sure wish I didn't delete your other post!
Edit: Those values were from the number overflowing 32 bits - your
program will never reach the correct answer. :(
The sum of a series of numbers from [1,b] is equal to:
( b^2 + b ) / 2
Therefor, if b > (2^16 - 1) then the sum will not fit into 32 bits.
Edit: Those values were from the number overflowing 32 bits - your
program will never reach the correct answer. :(
The sum of a series of numbers from [1,b] is equal to:
( b^2 + b ) / 2
Therefor, if b > (2^16 - 1) then the sum will not fit into 32 bits.
Slightly faster FPU only version: ;)
...and I just thought of even a faster way, but
it is a little trickier...
ACM_138 MACRO
LOCAL MainLoop,iLoop,ACM_Template
sub esp,4*3
FPU_CW EQU <word ptr [esp + 8]>
FPU_CWt EQU <word ptr [esp + 10]>
xor ebx,ebx ; output line counter
fld1
fld1
; set round mode to truncate
fstcw FPU_CW ; save for restore
fstcw FPU_CWt ; save for modify
and FPU_CWt,0F0FFh
or FPU_CWt, 0E00h ; truncate/53-bit for 10 output lines
; or FPU_CWt, 0F00h ; truncate/64-bit for 11 output lines
fldcw FPU_CWt
MainLoop:
fadd st,st(1) ; b 1
fld st ; b b 1
fmul st,st ; b^2 b 1
fadd st,st ; 2b^2 b 1
fld st ; 2b^2 2b^2 b 1
fsqrt ; c 2b^2 b 1
frndint ; c 2b^2 b 1
fld st ; c c 2b^2 b 1
fadd st,st(4) ; c+1 c 2b^2 b 1
fmul ; (c+1)c 2b^2 b 1
fsub ; ? b 1
fistp QWORD PTR [esp] ; b 1
mov eax,[esp]
or eax,[esp + 4]
jne MainLoop
fld st
fmul st,st
fadd st,st
fsqrt
frndint
fistp DWORD PTR [esp+4] ; b 1
fist DWORD PTR [esp] ; b 1
mov edx,[esp + 4] ; c
mov ecx,[esp] ; b
;; Output will consist of 10 lines each containing a pair of numbers,
;; each printed right justified in a field of width 10.
_CONST SEGMENT
ACM_Template db "%10.ld%10.ld",0
_CONST ENDS
inc ebx ; line counter
invoke wsprintf,OFFSET ACM_Buff,OFFSET ACM_Template,ecx,edx
invoke DebugPrint,OFFSET ACM_Buff
cmp ebx,10
jne MainLoop
fcompp
fldcw FPU_CW
add esp,4*3
ENDM...and I just thought of even a faster way, but
it is a little trickier...
Can't wait to check this out...
Btw, I was in the process of thinking of a formula for this set of numbers when yyou posted it...
Just curious how you did the math...
(I wouldn't have gotten it because my data was wrong (32 bit overflow problem)...
Sliver
Btw, I was in the process of thinking of a formula for this set of numbers when yyou posted it...
Just curious how you did the math...
(I wouldn't have gotten it because my data was wrong (32 bit overflow problem)...
Sliver
Sum of series = (h^2 + h + g - g^2)/2
For example: [1,6] = 1+2+3+4+5+6 = (36 + 6 + 1 - 1)/2 = 21
House Number = b
Last Number = c
We have two series: sum([1, (b-1)]) = sum([(b+1), c])
This results in:
2 b^2 = c^2 + c
Solve for integers.
For example: [1,6] = 1+2+3+4+5+6 = (36 + 6 + 1 - 1)/2 = 21
House Number = b
Last Number = c
We have two series: sum([1, (b-1)]) = sum([(b+1), c])
This results in:
2 b^2 = c^2 + c
Solve for integers.