Reverse a number

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

Re: Reverse a number

Postby RockTheSchock » Jul 13, 2015 16:39

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 ReverseType
Declare Operator Cast() As String
   value As ULongInt
   length As Integer
End Type

Operator ReverseType.Cast() As String
   Dim As String number = Str(value)
   Return String(length-Len(number),"0") + number
End Operator


Function _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]:Next
Return ValULng(s)
End Function

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

Function 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 rt
End Function

Dim As ULongInt n=1844674407370955161


Randomize 1

Dim As ULongInt tmp
Dim As ReverseType tmprt
Do
   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 500
Loop Until InKey=Chr(27)

Sleep
Tourist Trap
Posts: 2817
Joined: Jun 02, 2015 16:24

Re: Reverse a number

Postby Tourist Trap » Jul 13, 2015 17:39

@RockTheSchock, little erratum to code above :

Code: Select all

   t=Timer               ''....Add this here
Sleep 50
For z As Integer=1 To 100000
      tmp =_reverse_(n)
Next z
Print Timer-t,tmp
Print
n=Rnd*1844674407370955161
Sleep 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

Postby Tourist Trap » Jul 14, 2015 20:26

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 \ 10

Sleep

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

Re: Reverse a number

Postby counting_pine » Jul 14, 2015 22:15

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

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests