## Reverse a number

General FreeBASIC programming questions.
RockTheSchock
Posts: 226
Joined: Mar 12, 2006 16:25

### Re: Reverse a number

Tourist Trap wrote:However given a num and using its string conversion, strnum, left aside any speed considerations, I see some advantages :
• you can compute length(num) = len(strnum), which won't work directly since len(num) will return in fact len(numtype)
• you won't loose the terminal zeros when displaying : reversal(10000) = 1, whereas reversal(str(10000)) = "00001"
• you will be able to use string functions to work inside the number - if needed can save programing time
At least this is how I get the example below to work. Making first an array of digits, than reversing the array. Which seems finally after testing very close to the basic string reversal ...

if you compute a lot of reverse numbers but discard most or display just a few you could safe the length and use it when casting to a string.

Code: Select all

`Type ReverseTypeDeclare Operator Cast() As String   value As ULongInt   length As IntegerEnd TypeOperator ReverseType.Cast() As String   Dim As String number = Str(value)   Return String(length-Len(number),"0") + numberEnd OperatorFunction _reverse_(n As ULongInt) As ULongInt   Var s=Str(n)   Var lens=Len(s)For n As Integer=0 To (lens-1)\2:Swap s[n],s[lens-1-n]:NextReturn ValULng(s)End FunctionFunction ReverseIRCVS( ByVal Num_ As ULongInt ) As ULongInt   Dim As ULongInt temp_ = Num_   Dim As ULongInt reverse_ = 0   '::::::::::::::::::::::::::::::::::::::::::::::::   'Reverse a number !!!   While temp_ <> 0      reverse_ = (reverse_ * 10) + (temp_ Mod 10)      temp_ = Int(temp_/10)   Wend   '::::::::::::::::::::::::::::::::::::::::::::::::   Return reverse_End Function 'ULONGINT := ReverseIRCVS(ULONGINT)Function ReverseIRCVS2( ByVal Temp_ As ULongInt ) As ULongInt   'Dim As ULongInt temp_ = Num_   Dim As ULongInt reverse_ '= 0   '::::::::::::::::::::::::::::::::::::::::::::::::   'Reverse a number !!!   While temp_ <> 0      reverse_= reverse_ Shl 3+reverse_ Shl 1  + (temp_ Mod 10) '=  reverse_*8 +  reverse_ * 2      temp_ =temp_\10   Wend   '::::::::::::::::::::::::::::::::::::::::::::::::   Return reverse_End FunctionFunction ReverseIRCVS3( ByVal Temp_ As ULongInt ) As ReverseType   Static rt As ReverseType   'Dim As ULongInt temp_ = Num_   Dim As ULongInt reverse_ '= 0   Dim As Integer i=0   '::::::::::::::::::::::::::::::::::::::::::::::::   'Reverse a number !!!   While temp_ <> 0      i+=1      reverse_= reverse_ Shl 3+reverse_ Shl 1  + (temp_ Mod 10) '=  reverse_*8 +  reverse_ * 2      temp_ =temp_\10   Wend   '::::::::::::::::::::::::::::::::::::::::::::::::   rt.value = reverse_   rt.length = i   Return rtEnd FunctionDim As ULongInt n=1844674407370955161Randomize 1Dim As ULongInt tmpDim As ReverseType tmprtDo   Print "Number is "; n   Print   Dim As Double t=Timer   For z As Integer=1 To 100000      tmprt=ReverseIRCVS3(n)   Next z   Print Timer-t,tmprt.value;tmprt.length,tmprt   Sleep 50   t=Timer   For z As Integer=1 To 100000      tmp =ReverseIRCVS2(n)   Next z   Print Timer-t,tmp   Sleep 50   t=Timer   For z As Integer=1 To 100000      tmp =ReverseIRCVS(n)   Next z   Print Timer-t,tmp   Sleep 50   For z As Integer=1 To 100000      tmp =_reverse_(n)   Next z   Print Timer-t,tmp   Print   n=Rnd*1844674407370955161   Sleep 500Loop Until InKey=Chr(27)Sleep`
Tourist Trap
Posts: 2817
Joined: Jun 02, 2015 16:24

### Re: Reverse a number

@RockTheSchock, little erratum to code above :

Code: Select all

`   t=Timer               ''....Add this hereSleep 50For z As Integer=1 To 100000      tmp =_reverse_(n)Next zPrint Timer-t,tmpPrintn=Rnd*1844674407370955161Sleep 500`

If you're using len(str(num))-len(str(reverse)) to compute how many zero to prepend, that seems to me a nice way. For the details it's rather sophisticated!

I've improved the string based method. And it's 'only' 2-3 times slower than IRCVS now. However there is a bug I cant get rid off. I'll try to expose it later. It is why I had to split the loop in 2 parts in the procedure.

Code: Select all

`    '    'Prog to compare 2 number-reversal methods    '    Function ReverseIRCVS( ByVal Num_ As ULongInt ) As ULongInt        Dim As ULongInt temp_ = Num_        Dim as ULongInt reverse_ = 0        '::::::::::::::::::::::::::::::::::::::::::::::::       'Reverse a number !!!            While temp_ <> 0              reverse_ = (reverse_ * 10) + (temp_ Mod 10)              temp_ = Int(temp_/10)              Wend        '::::::::::::::::::::::::::::::::::::::::::::::::       Return reverse_    End Function 'ULONGINT := ReverseIRCVS(ULONGINT)    Function ReverseYetAnotherStringMethod( ByVal Num_ As ULongInt ) As ULongInt        Dim as ULongInt reverse_ = 0        Dim As String numString_ = Str(Num_)          Dim As Integer lenNumString = Len(numString_)        'straightforward solution is loosing precision in last digits (rounding issue ????)        '  For _i As Integer = 1 To lenNumString      '       reverse_ += 10^(lenNumString-_i)*(numString_[lenNumString-_i] - 48)      '  Next _i               Dim As String numStringSplit1 = Left(numString_, 5)        Dim As ULongInt rev1_, rev2_                For _i As Integer = 1 To lenNumString-5             reverse_ += 10^(lenNumString-_i)*(numString_[lenNumString-_i] - 48)        Next _i          rev1_=reverse_         reverse_ = 0        For _i As Integer = 1 To 5             reverse_ += 10^(5-_i)*(numStringSplit1[5-_i] - 48)        Next _i         rev2_ = reverse_         reverse_ = rev1_ + rev2_        Return reverse_    End Function 'ULONGINT := ReverseOtherMethod(ULONGINT)    ''_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_    Cls    Randomize Timer    Dim As String _inkey = ""    Dim As Double t1_ = 0    Dim As Double t2_ = 0    Dim As ULongInt number_ , reverse_    Do        number_ = 1e+9 + CULngInt (Rnd * 109999999900000000)        Locate 2, 4 : ? "  +--------+"        Locate 3, 4 : ? " / NUMBER /" & Space(10) & number_        Locate 4, 4 : ? "+--------+ "        Locate 6, 4 : ? "  +---------+"        Locate 7, 4 : ? " / REVERSE /"        Locate 8, 4 : ? "+---------+ "                t1_ = Timer         reverse_ = ReverseIRCVS( number_ )         t1_ = Timer - t1_         Locate 7, 4 : ? Tab(19); "IRCVS "; reverse_         Locate 8, 4 : ? Tab(24); t1_  * 1e+6                t2_ = Timer         reverse_ = ReverseYetAnotherStringMethod( number_ )         t2_ = Timer - t2_         Locate 10, 4 : ? Tab(19); "Other ";  reverse_         Locate 11, 4 : ? Tab(24); t2_ * 1e+6                ? : ? : ? "    Time ratio : "; t2_ / t1_         ? : ? : ? "    [SPACE] to pause, then [ESC]x2 to quit"         _inkey = Inkey         Sleep 2000         Sleep -(InKey=Chr(32))*15000    Loop Until _inkey = Chr(27)    ? "......END"    Sleep : End    ''_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_=_     `
Tourist Trap
Posts: 2817
Joined: Jun 02, 2015 16:24

### Re: Reverse a number

Ok, I think I've found the type of problem that is occuring in my procedures when I'm multiplying by powers of 10 a very big ulongint, probably close to the max value. Best to understand is to run this little test.

Code: Select all

`Dim As ULongInt ulgintMax = 18446744073709551615? "ulgintMax>" ;ulgintMax? "ulgintMax + 1>" ; ulgintMax + 1? "ulgintMax * (10 \ 10)>" ; ulgintMax * (10 \ 10)? "ulgintMax * 10 \ 10>" ; ulgintMax * 10 \ 10Sleep `

ulgintMax * 10 \ 10 is not equal to ulgintMax , which is in my opinion where I've been loosing digits...
counting_pine
Posts: 6180
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Reverse a number

Yeah, you'll necessarily run into trouble if the reversed number is larger than 2^64-1.
You may also lose accuracy by doing floating point divisions. The compiler could rightfully truncate precision to 53 bits. Better to use integer division instead - a \ b instead of Int(a / b).
Technically, a \ b is mathematically closer to Fix(a / b), but there is no difference if the result is non negative (which it must be if it's unsigned.)