Assembly

Assembly RSS

How quickly can you code this?

Please support our Assembly advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Mar 2005

Posts: 129

Reputation: Evenbit is on a distinguished road

Solved Threads: 4

Evenbit

Offline

Junior Poster

How quickly can you code this?

Sep 6th, 2008

It's a FizzBuzz question designed to "separate the men from the boys", so don't cheat.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Nathan.

while (CPU is present) {some assembly required}

•

Join Date: Mar 2005

Posts: 129

Reputation: Evenbit is on a distinguished road

Solved Threads: 4

Evenbit

Offline

Junior Poster

Re: How quickly can you code this?

Sep 9th, 2008

I posted this because I consider it a "trick question" to some extent. As we hone our "problem-solving" skills, it is natural for us to attempt a clever solution. All too often, however, clever means that we spend too much time on the issue and introduce more opportunities for bugs to creep into the code. Sometimes, we don't see the obvious, simple solution. And I believe that this question is really intended to test "basic skills" rather than discover brilliance.

Here is the FizzBuzz article:

http://imranontech.com/2007/01/24/us...o-grok-coding/

Notice that most of the comments at the bottom present solutions using the modulus operation and other tricks? If you attack the issue using the KISS (Keep It Simple Smarty) principle, you'll see that simple subtraction is all that is necessary.

In Ruby:

 Help with Code Tags 
 Assembly Syntax (Toggle Plain Text) 
fizz = 3
buzz = 5
1.upto( 100 ) do |i|
  fizz -= 1
  buzz -= 1
  if fizz == 0 and buzz == 0
    puts "fizzbuzz"
    fizz = 3
    buzz = 5
  elsif fizz == 0
    puts "fizz"
    fizz = 3
  elsif buzz == 0
    puts "buzz"
    buzz = 5
  else
    puts i
  end
end
fizz = 3
buzz = 5
1.upto( 100 ) do |i|
  fizz -= 1
  buzz -= 1
  if fizz == 0 and buzz == 0
    puts "fizzbuzz"
    fizz = 3
    buzz = 5
  elsif fizz == 0
    puts "fizz"
    fizz = 3
  elsif buzz == 0
    puts "buzz"
    buzz = 5
  else
    puts i
  end
end

Nathan.

while (CPU is present) {some assembly required}

•

Join Date: Feb 2005

Posts: 199

Reputation: Tight_Coder_Ex is an unknown quantity at this point

Solved Threads: 14

Tight_Coder_Ex Tight_Coder_Ex is offline

Offline

Junior Poster

Re: How quickly can you code this?

Sep 10th, 2008

Here is my version of FizzBuss and it took me 2 1/2 hrs. I've read these little
blurbs about how this is used to test potential programmers and in fact the
overall method only took me 20 seconds to determine, but utilizing instructions
that are availiable in later CPU's took a little longer.

If there is interest in this thread I look forward to seeing others optimizations
that are tighter than mine (in ASM) and would probably work on my own version
that is better.

 Help with Code Tags 
 asm Syntax (Toggle Plain Text) 
; Written using ML
 
		.686P
		.model flat, stdcall
		option casemap:none
 
	include	windows.inc
	include	kernel32.inc
	include	user32.inc
 
	includelib kernel32.lib
	includelib user32.lib
 
	Main	proto
	Print	proto	:DWORD
 
		.data
 
 Prompt1	db	13, 10, 13, 10, '3 & 5s Multiples', 13, 10
		db	'----------------', 13, 10, 0
 Epilogue	db	13, 10, '-- DONE --', 13, 10, 13, 10, 0
 
 Prompt2	db	'Fiss', 0
 Prompt3	db	'Buzz', 0
 CRLF		db	13, 10, 0
 FMT		db	'%4d', 0
 
		.data?
 
  StdOut	dd	?
 
		.code
; =============================================================================
 
  start:	invoke	GetStdHandle, STD_OUTPUT_HANDLE
		mov	StdOut, eax
		invoke	Print, offset Prompt1
		invoke	Main
		invoke	Print, offset Epilogue
		ret
 
;------------------------------------------------------------------------------
  Main		proc
 
		xor	eax, eax	; Intiialize working registers
		mov	ecx, eax
 		xor	 cx, 801H
 
	L1:	inc	eax		; bump counter
		cmp	 al, 100
		ja	Done		; and process till 100
 
		invoke	Print, offset CRLF	; append CRLF to previous output
 
 		shl	 cx, 1		; Shift mask bits for 3's & 5's
		pushfd
		btr	ecx, 3		; Test bit 3 and compliment if on
		jnc	@F		; NC if not divisible by 3
 
		invoke	Print, offset Prompt2	; Print prompt 'Fiss'
		or	 cl, 1		; Reset mask
		bts	ecx, 31		; and let remainder of loop know
 
	@@:	popfd		; Restore flag from previous condition
		jnc	@F	; and jump if bit hasn't shifted out
 
		invoke	Print, offset Prompt3
		or	ecx, 80000800H		; Reset orginal mask for 5's
 
	@@:	btr	ecx, 31	; Test and reset if 'Fiss' printed
		jc	L1		; If bit was on skip printing number
 
	; Print right justifed number that is not divisible by 3 or 5
		push	eax
		push	ecx
		enter	20h, 0
		mov	edx, esp
		invoke	wsprintf, edx, ADDR FMT, eax
		invoke	Print, esp
		leave
		pop	ecx
		pop	eax
		jmp	L1
 
  Done:		ret				; Done
 
  Main		endp
 
; -----------------------------------------------------------------------------
  Print		proc	uses eax ecx lpszText:DWORD
 
	LOCAL	Written:DWORD
 
		invoke	lstrlen, lpszText
		push	NULL
		lea	ecx, Written
		push	ecx
		push	eax
		push	lpszText
		push	StdOut
		call	WriteFile
		ret
 
  Print		endp
 
	end start
; Written using ML

		.686P
		.model flat, stdcall
		option casemap:none

	include	windows.inc
	include	kernel32.inc
	include	user32.inc

	includelib kernel32.lib
	includelib user32.lib

	Main	proto
	Print	proto	:DWORD

		.data

 Prompt1	db	13, 10, 13, 10, '3 & 5s Multiples', 13, 10
		db	'----------------', 13, 10, 0
 Epilogue	db	13, 10, '-- DONE --', 13, 10, 13, 10, 0

 Prompt2	db	'Fiss', 0
 Prompt3	db	'Buzz', 0
 CRLF		db	13, 10, 0
 FMT		db	'%4d', 0

		.data?

  StdOut	dd	?

		.code
; =============================================================================

  start:	invoke	GetStdHandle, STD_OUTPUT_HANDLE
		mov	StdOut, eax
		invoke	Print, offset Prompt1
		invoke	Main
		invoke	Print, offset Epilogue
		ret

;------------------------------------------------------------------------------
  Main		proc

		xor	eax, eax	; Intiialize working registers
		mov	ecx, eax
 		xor	 cx, 801H

	L1:	inc	eax		; bump counter
		cmp	 al, 100
		ja	Done		; and process till 100

		invoke	Print, offset CRLF	; append CRLF to previous output

 		shl	 cx, 1		; Shift mask bits for 3's & 5's
		pushfd
		btr	ecx, 3		; Test bit 3 and compliment if on
		jnc	@F		; NC if not divisible by 3

		invoke	Print, offset Prompt2	; Print prompt 'Fiss'
		or	 cl, 1		; Reset mask
		bts	ecx, 31		; and let remainder of loop know

	@@:	popfd		; Restore flag from previous condition
		jnc	@F	; and jump if bit hasn't shifted out

		invoke	Print, offset Prompt3
		or	ecx, 80000800H		; Reset orginal mask for 5's

	@@:	btr	ecx, 31	; Test and reset if 'Fiss' printed
		jc	L1		; If bit was on skip printing number

	; Print right justifed number that is not divisible by 3 or 5
		push	eax
		push	ecx
		enter	20h, 0
		mov	edx, esp
		invoke	wsprintf, edx, ADDR FMT, eax
		invoke	Print, esp
		leave
		pop	ecx
		pop	eax
		jmp	L1

  Done:		ret				; Done

  Main		endp

; -----------------------------------------------------------------------------
  Print		proc	uses eax ecx lpszText:DWORD

	LOCAL	Written:DWORD

		invoke	lstrlen, lpszText
		push	NULL
		lea	ecx, Written
		push	ecx
		push	eax
		push	lpszText
		push	StdOut
		call	WriteFile
		ret

  Print		endp

	end start

•

Join Date: Mar 2005

Posts: 129

Reputation: Evenbit is on a distinguished road

Solved Threads: 4

Evenbit

Offline

Junior Poster

Re: How quickly can you code this?

Sep 11th, 2008

The first rule of code optimization is:

Eliminate conditional branches. Use lookup-tables instead.

The second rule of code optimization is:

If possible, remove any loops.

So, keeping to the KISS philosophy, here is my quick code:

 Help with Code Tags 
 Assembly Syntax (Toggle Plain Text) 
; For Windows:
;  nasm -f win32 -o fizzbuzz.obj fizzbuzz.asm
;  gcc -o fizzbuzz.exe fizzbuzz.obj
 
; For Linux:  (remove all "_" underscores from this source)
;  nasm -f elf -o fizzbuzz.o fizzbuzz.asm
;  gcc -o fizzbuzz fizzbuzz.o
 
section .data
 
one:	db	'1',10,'2',10,'Fizz',10,'4',10,'Buzz',10,
	db	'Fizz',10,'7',10,'8',10,'Fizz',10,'Buzz',10,'',0
two:	db	'11',10,'Fizz',10,'13',10,'14',10,'FizzBuzz',10,
	db	'16',10,'17',10,'Fizz',10,'19',10,'Buzz',10,'',0
three:	db	'Fizz',10,'22',10,'23',10,'Fizz',10,'Buzz',10,
	db	'26',10,'Fizz',10,'28',10,'29',10,'FizzBuzz',10,'',0
four:	db	'31',10,'32',10,'Fizz',10,'34',10,'Buzz',10,
	db	'Fizz',10,'37',10,'38',10,'Fizz',10,'Buzz',10,'',0
five:	db	'41',10,'Fizz',10,'43',10,'44',10,'FizzBuzz',10,
	db	'46',10,'47',10,'Fizz',10,'49',10,'Buzz',10,'',0
six:	db	'Fizz',10,'52',10,'53',10,'Fizz',10,'Buzz',10,
	db	'56',10,'Fizz',10,'58',10,'59',10,'FizzBuzz',10,'',0
seven:	db	'61',10,'62',10,'Fizz',10,'64',10,'Buzz',10,
	db	'Fizz',10,'67',10,'68',10,'Fizz',10,'Buzz',10,'',0
eight:	db	'71',10,'Fizz',10,'73',10,'74',10,'FizzBuzz',10,
	db	'76',10,'77',10,'Fizz',10,'79',10,'Buzz',10,'',0
nine:	db	'Fizz',10,'82',10,'83',10,'Fizz',10,'Buzz',10,
	db	'86',10,'Fizz',10,'88',10,'89',10,'FizzBuzz',10,'',0
ten:	db	'91',10,'92',10,'Fizz',10,'94',10,'Buzz',10,
	db	'Fizz',10,'97',10,'98',10,'Fizz',10,'Buzz',10,'',0
 
section .text
 
	global _main
	extern _printf
 
_main:
	push one
	call _printf
	add esp, 4
	push two
	call _printf
	add esp, 4
	push three
	call _printf
	add esp, 4
	push four
	call _printf
	add esp, 4
	push five
	call _printf
	add esp, 4
	push six
	call _printf
	add esp, 4
	push seven
	call _printf
	add esp, 4
	push eight
	call _printf
	add esp, 4
	push nine
	call _printf
	add esp, 4
	push ten
	call _printf
	add esp, 4
 
	xor eax, eax
	ret
; For Windows:
;  nasm -f win32 -o fizzbuzz.obj fizzbuzz.asm
;  gcc -o fizzbuzz.exe fizzbuzz.obj

; For Linux:  (remove all "_" underscores from this source)
;  nasm -f elf -o fizzbuzz.o fizzbuzz.asm
;  gcc -o fizzbuzz fizzbuzz.o

section .data

one:	db	'1',10,'2',10,'Fizz',10,'4',10,'Buzz',10,
	db	'Fizz',10,'7',10,'8',10,'Fizz',10,'Buzz',10,'',0
two:	db	'11',10,'Fizz',10,'13',10,'14',10,'FizzBuzz',10,
	db	'16',10,'17',10,'Fizz',10,'19',10,'Buzz',10,'',0
three:	db	'Fizz',10,'22',10,'23',10,'Fizz',10,'Buzz',10,
	db	'26',10,'Fizz',10,'28',10,'29',10,'FizzBuzz',10,'',0
four:	db	'31',10,'32',10,'Fizz',10,'34',10,'Buzz',10,
	db	'Fizz',10,'37',10,'38',10,'Fizz',10,'Buzz',10,'',0
five:	db	'41',10,'Fizz',10,'43',10,'44',10,'FizzBuzz',10,
	db	'46',10,'47',10,'Fizz',10,'49',10,'Buzz',10,'',0
six:	db	'Fizz',10,'52',10,'53',10,'Fizz',10,'Buzz',10,
	db	'56',10,'Fizz',10,'58',10,'59',10,'FizzBuzz',10,'',0
seven:	db	'61',10,'62',10,'Fizz',10,'64',10,'Buzz',10,
	db	'Fizz',10,'67',10,'68',10,'Fizz',10,'Buzz',10,'',0
eight:	db	'71',10,'Fizz',10,'73',10,'74',10,'FizzBuzz',10,
	db	'76',10,'77',10,'Fizz',10,'79',10,'Buzz',10,'',0
nine:	db	'Fizz',10,'82',10,'83',10,'Fizz',10,'Buzz',10,
	db	'86',10,'Fizz',10,'88',10,'89',10,'FizzBuzz',10,'',0
ten:	db	'91',10,'92',10,'Fizz',10,'94',10,'Buzz',10,
	db	'Fizz',10,'97',10,'98',10,'Fizz',10,'Buzz',10,'',0

section .text

	global _main
	extern _printf

_main:
	push one
	call _printf
	add esp, 4
	push two
	call _printf
	add esp, 4
	push three
	call _printf
	add esp, 4
	push four
	call _printf
	add esp, 4
	push five
	call _printf
	add esp, 4
	push six
	call _printf
	add esp, 4
	push seven
	call _printf
	add esp, 4
	push eight
	call _printf
	add esp, 4
	push nine
	call _printf
	add esp, 4
	push ten
	call _printf
	add esp, 4

	xor eax, eax
	ret

Nathan.

Last edited by Evenbit; Sep 11th, 2008 at 12:58 am. Reason: format

while (CPU is present) {some assembly required}

•

Join Date: Feb 2005

Posts: 199

Reputation: Tight_Coder_Ex is an unknown quantity at this point

Solved Threads: 14

Tight_Coder_Ex Tight_Coder_Ex is offline

Offline

Junior Poster

Re: How quickly can you code this?

Sep 11th, 2008

Interesting Nathan, however your example renders the computer redundant as you've already done the calculating, therefore a word processor would have been a better choice.

I do agree with your points of optimization and size should be included in there somewhere too, but at the end of the day examples should always exemplify the computers underlying premise, in that it does the computing.

Hypothetically, we are working in an IT department and now charged with modifying our applications to be dynamic in nature. IE: operator selectable range and pairs of factors (30,000 -> 200,000 & 8's and 18's). My application may increase in size to possibly 1500 bytes, yours would be 3.7 megs 2,500 times larger than mine.

I not beginning to suggest my code is the best or even better example, but rather optimization is far more encompassing and if I were to be in an interview and the recruiter was to evaluate my abilities based on "FIZZBUZZ", I would just simply get up and leave the room.

There doesn't seem to be much interest from others, but in the spirit of competition why don't we modify our applications to be dynamic as indicated above, post our examples and maybe if we are lucky we can have others critique them.

Criteria: User defined range
User defined factors to a maximum of 12

Tabbed output ie:

1
2
3 Fizz
4
5 Buzz
6 Fizz
7
8
9 Fizz
10 Buzz
11
12 Fizz
13
14
15 Fizz Buzz

Note: digits should be right justified, formatting is removing spaces I've entered.

•

Join Date: Mar 2005

Posts: 129

Reputation: Evenbit is on a distinguished road

Solved Threads: 4

Evenbit

Offline

Junior Poster

Re: How quickly can you code this?

Sep 21st, 2008

•

Originally Posted by Tight_Coder_Ex

Interesting Nathan, however your example renders the computer redundant as you've already done the calculating, therefore a word processor would have been a better choice.

Ah, but my example stays within the specs. The question said *nothing* about the data being pre-computed or not:

 Help with Code Tags 
 Assembly Syntax (Toggle Plain Text) 
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

•

I do agree with your points of optimization and size should be included in there somewhere too, but at the end of the day examples should always exemplify the computers underlying premise, in that it does the computing.

Oh, but it did do the computing. I simply used the output of my previous example (with a small bit of search-n-replace) to write the code for my last example. Making use of "code-writing tools" is also a good skill to possess.

•

I not beginning to suggest my code is the best or even better example, but rather optimization is far more encompassing and if I were to be in an interview and the recruiter was to evaluate my abilities based on "FIZZBUZZ", I would just simply get up and leave the room.

I imagine they wouldn't be interested in testing your code-optimization skills because they'd already know/expect you have them.

•

There doesn't seem to be much interest from others, but in the spirit of competition why don't we modify our applications to be dynamic as indicated above, post our examples and maybe if we are lucky we can have others critique them.

Criteria: User defined range
User defined factors to a maximum of 12

Now you have changed the specs!

I am not optimistic about people's interest in optimization. Heck, I once had an idea that list processing (parsing) would be easier and maybe faster if I used "repne scasd" provided all the words in the list were four characters or less. However, modern processors focus on optimizing discrete coded loops -- so the old "string" instructions are sluggish. Most of the time, one will be more "ahead of the ball" by concentrating on design issues like optimal data structures, overall data flow (paying attention to cache hit/miss), and reducing complexity.

Nathan.

while (CPU is present) {some assembly required}