ASM Community

Getting tired of searching for an effective algorithm which calculates the number of digits of a 64-Bit-unsigned-integer but
finding only long-winded binary-to-string-to-binary conversion routines I wrote my own one.

The decimal part uses the coprocessor using this simple formula:

numdigits = int(log(number64))+1

The hexadecimal part uses the powerful BSR ("bit scan reverse") instruction, which can also be considered as binary logarithm.

Input: EAX=Pointer qword ptr
Output: EAX=number of digits
Changed: EAX, EDX, FPU(S0...S2)

Written for TASM, 32Bit.

Thanks for any comments or suggestions.

fpu_ctrlword	record fpucw_$1:3,fpucw_ic:1,fpucw_rc:2,fpucw_pc:2,fpucw_ie:1,fpucw_$2:1,fpucw_pm:1,fpucw_um:1,fpucw_om:1,fpucw_zm:1,fpucw_dm:1,fpucw_im:1

;number64	dq 12345678901234
number64 dq 01fh

main		proc @type_main argc:dword,argv:dword,argenv:dword
	mov eax,offset number64
	fninit

;----Start Decimal part----------------------------------------------------------------------------
	push dx		;make room for FPU control word
	fnstcw	;save FPU control word
	push word ptr	;create a copy of FPU control word
	setflag word ptr,3 shl fpucw_rc		;set FPU rounding mode: truncate
	fldcw	;set the FPU rounding moude
	fld1		;"1"
	fldlg2	;log(2) = 1/log(2,10)
	fild qword ptr 	;load number64
	ftst		;test if number64 equals to zero
	fnstsw ax
	sahf		;set processor flags to FPU result for evaluation
	.if zero?
		fcompp	;throw away s0 and s1, leave "1"
	.else
		fyl2x		;s1 * log(2,s0) = log(2,s0) / log(2,10) = log(s0)
		fadd		;= log(s0)+1
	.endif
	fistp word ptr
	xor eax,eax
	pop ax	;load EAX with num of digits
	fldcw	;restore FPU control word
	pop dx	;throw away FPU control word space
;----End Decimal part----------------------------------------------------------------------------

	mstr s1,<"The number %I64u contains %d decimal digits.",10>
	call printf,offset s1,dword ptr number64+4 dword ptr number64,eax


	mov eax,offset number64

;----Start Hexadecimal part----------------------------------------------------------------------------
	xor edx,edx		;initialize digit counter value in case number64 equals to zero
	bsr edx,dword ptr	;search for the first set bit in HIGH_DWORD
	.if zero?	;no bit was set
		bsr edx,dword ptr	;search the first set bit in LOW_DWORD
	.else
		add edx,32
	.endif
	xchg eax,edx
	shr eax,2
	inc eax
;----End Hexadecimal part----------------------------------------------------------------------------
	
	mstr s2,<"The number %I64Xh contains %d hexadecimal digits.">
	call printf,offset s2,dword ptr number64+4 dword ptr number64,eax

endmain:	ret
endp

That's fully correct. I overlooked this case. But assuming that such a large 64Bit unsigned number will never be committed to the procedure and a programmer pays attention to the argument I think "fabs" can be omitted for code space.

Yes, certainly. You are in the wrong thread. But if you are able to program your "gpu" with this "texture" please post it here to suggest a better solution or leave this thread. Thank you.

Are you serious? If I get you right, a user shall buy a multi-monster-high-end-PC with a super-3D-power-wasting-multitexture-water-cooled graphic card just only to run a program which calculates the number of digits from a shitty integer? That's like breaking a butterfly on a wheel. But thanks for the proposal.

How about something like this:

mov edx,dword ptr ; load hi-dword
mov eax,dword ptr ; load lo-dword

.if edx==0
     cmp eax,10
     jl _numDigitsIs1
     cmp eax,100
     jl _numDigitsIs2
     cmp eax,1000
     jl _numDigitsIs3
     cmp eax,10000
     jl _numDigitsIs4
...
.else
   .. here in a bit more complicated way compare to 64-bit values
.endif

Just an idea. May be faster, may be slower, may be optimized, may lead to tricks


Homer: GPUs can only handle single-precision floats, only 2 recent ones added double-precision floats. You can't even do bit-fiddling ops like XOR/AND/OR. Maybe, just maybe that functionality is exposed/emulated in CUDA, but GL_NV_fragment_program4's doc only rejects that notion.
Whoops, it's documented in GL_NV_gpu_program4  - it has xor/and/or/not instructions

Quite the contrary, the GPU would not be fast for this at all. Way too much latency to seriously consider it for doing non-parallel work.

Using the slow-assed div instruction and dividing by 10 until the quotient is 0 would be many times faster that trying to shuttle data over to the GPU, running a shader, and then shuttling a result back.

I'm sure that GPGPU is all cool and shit, but come on... be realistic... it aint cool this time.. it would be a novel solution with no practical value at all

Consider that a 10-bit number can range from 512..1023

..so is a 10-bit number 3 digits, or 4? How will a lookup table help while still fitting on a practical storage medium (a 1TB drive wouldn't be big enough, would it?)

Note the relationship between base-2 and base-16 that makes his hex techique possible.

MASM

.data
??pow10 textequ <1>
POW10TABLE dq ??pow10
rept 19
	??pow10 CatStr ??pow10,<0>
	%dq ??pow10
endm

.code
UInt64Log10 proc uses ebx edi esi uint64:qword
	mov eax,dword ptr uint64
	mov edx,dword ptr uint64+4
	lea ebx,POW10TABLE
	.if edx
		bsr ecx,edx
		add ecx,32+1
		imul ecx,ecx,1233
		shr ecx,12
		mov esi,eax
		mov edi,edx
		sub esi,
		sbb edi,
@@:		shr edi,31
		sub ecx,edi
		mov eax,ecx
		ret
	.endif
	bsr ecx,eax
	add ecx,1
	imul ecx,ecx,1233
	shr ecx,12
	mov edi,eax
	sub edi,
	jmp @B
	
UInt64Log10 endp

UInt64Log2 proc uint64:qword
	mov edx,dword ptr uint64+4;hi
	mov eax,dword ptr uint64;lo
	cmp edx,1; if (edx<1) { carry=1 } else { carry=0 } 
	cmovnc eax,edx
	sbb edx,edx; set to -1 if carry
	bsr eax,eax
	and edx,-32
	lea eax,
	ret
UInt64Log2 endp

That's the best solution I have ever seen!

Neither nVidia nor ATi support 128 bit floats, as far as I know.
Their hardware normally works with 32-bit floats, but with GPGPU tasks they can process 64-bit precision at reduced performance.
I also don't know of any textures formats that would support 128 bit float.
4x real4 is not the same as 1x real16. You couldn't do a 128 bit log operation on the data.