Sorry,

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.

**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.

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 start

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

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

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 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?

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

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 :)

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!

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 - yourprogram 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

;) Okay, this is really fast on an Athlon! ;)
...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.