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.
Posted on 2002-03-07 10:39:33 by bitRAKE
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



; #########################################################################

.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 start
Posted on 2002-03-07 12:23:18 by Sliver
I 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
Posted on 2002-03-07 12:30:46 by bitRAKE
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 :-)
Posted on 2002-03-07 12:41:06 by Sliver
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...
         6         8

35 49
204 288
1189 1681
6930 9800
40391 57121
Is my output after one minute, and nothing changes for twenty minutes...:(

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?
Posted on 2002-03-07 16:18:41 by bitRAKE
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
ENDM
Posted on 2002-03-07 23:21:56 by bitRAKE
I 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 :)
Posted on 2002-03-07 23:35:32 by Sliver
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.
Posted on 2002-03-07 23:52:47 by bitRAKE
Slightly faster FPU only version: ;)
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
;) Okay, this is really fast on an Athlon! ;)
...and I just thought of even a faster way, but
it is a little trickier...
Posted on 2002-03-08 01:24:54 by bitRAKE
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
Posted on 2002-03-08 14:44:08 by 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.
Posted on 2002-03-08 15:03:43 by bitRAKE