0

I have an algorithm that its main purpose is decoding, converting, or what have you a string of uppercase letters (A-Z) into a number. This is almost like converting a base 26 number into base 10, however I believe that a base 26 number encoded would actually include numbers, I am working strictly with uppercase letters, I digress.

I have an implantation working in C++11, in fact most of the controller algorithm was a direct copy, with a slight change to the indexOf method.

The C++11 version works as I expect it to. So initially I thought the new indexOf method was incorrect, but after a simple test, it is working as expected. I have narrowed down the problem to a line in the convertTo10 where I am calling the pow function.

As you can see from the Serial.println()'s in the convertTo10 method, the output is printing exactly what we expect, 0 & 26.

However, the output of this function is 25. WHAT?

I have read the docs on the pow method from the Arduino lib, and it takes in two floats and returns a double. Even if the issue was a type conversion issue, converting a double to an int truncates the number, it does not round it. Well, this is from working with C++.

Any help with this issue would be much appreciated.

#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <inttypes.h>

#include <Arduino.h>
#include <avr/pgmspace.h>
#include <Wire.h>


const char _values[26] = {
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
    'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
    'U', 'V', 'W', 'X', 'Y', 'Z'
};

const int _val_len = 26;


int indexOf(char needle);
int convertTo10(String value, int len);

String x = "BA";
int len = 2;

void loop() {  
  Serial.print(x);
  Serial.print("=> ");
  Serial.println(convertTo10(x, 2));
  delay(50000);
}

int convertTo10(String value, int len) {
    int lastIndex = len - 1;
    double output = 0;
    int pos = 0;
    Serial.println();
    for (int i = lastIndex; i >= 0; i--) {
        int r = indexOf(value[i]);

        output += (r * pow((_val_len, pos));
        Serial.print("     output => ");
        Serial.println( output );
        pos++;
    }
    return output;
}

int indexOf(char needle) {

    int first = 0; 
    int last = _val_len - 1; 
    int mid;  

  do {   
    mid = (first + last) / 2; 

    if (_values[mid] == needle)
      return mid;
    if (_values[mid] > needle)
      last = mid - 1;
    else
      first = mid + 1; 
  } while (first <= last);

  return -1; 
}

For Reference, Here what it is outputting:

BA =>
     output => 0.00
     output => 26.00 
25
  • 1
    Also posted on the Arduino Forum. – tttapa Dec 8 '17 at 0:46
  • You can make the return value be 26 in this case by rounding. That is change the last line of your conversion function to be: return round (output);. The fact that it is returning 25 indicates that the pow function is not giving an exact result. If you increase the number of decimal places printed you will see that you are actually getting 25.9999961853. – Nick Gammon Dec 8 '17 at 22:23
2

way too complicated:

int convertTo10(char *num_26, int len) {
  int tmp = 0;  //hold the output
  int i;  //indexing the input
  while (len--) tmp = tmp * 26 + (num_26[i++]-'A');
  return tmp;
}

note: 1. "* 26" can be further simplified;

  1. error checking could be built-in here, or somewhere else (better).

  2. better structuring could get rid of one of the temporary variables.

  • Thank you for the optimized code! However, I was hoping I could get an explanation on what is happening in the code I posted? What did I do wrong? – James Little Dec 8 '17 at 1:38
  • What you did wrong was to rely on a floating point number to be exact. They hardly ever are. – Delta_G Dec 8 '17 at 2:13
  • @Delta_G I realize this now. Thank you for the correction, I should have just waiting until the morning to revisit the problem, instead of ask dumb questions. I do appreciate the help. – James Little Dec 8 '17 at 2:39
  • @dannyf As much as I appreciate this solution and the time and effort you took to help me. I have to mark this solution as incorrect. I have verified that on a atmel2560 compiled with avr-gcc, and on Debian x64 compiled with g++ under standard 11, this method will always return 0. – James Little Dec 8 '17 at 15:12
  • This code fails because i is not initialized. Otherwise it is conceptually similar to my answer. If you change the third line to int i = 0; it works. – Nick Gammon Dec 8 '17 at 22:10
1

Your code is incredibly complex for a simple thing like converting a number from another base. This works (prints 26):

const char * test = "BA";

long convertTo10 (const char * s)
  {
  long result = 0;
  for (const char * p = s; *p; p++)
    {
    result *= 26;   // base
    result += *p - 'A';  // make zero-relative
    }
  return result;
  } // end of convertTo10

void setup() 
  {
  Serial.begin (115200);
  Serial.println ("Starting.");
  Serial.println (convertTo10 (test));
  }


void loop() { }

With input "CBA" it prints 1378 as expected. Sketch size: 2,300 bytes of program memory. The sketch size reduces to 2,236 bytes if I make the function return int (as you did) rather than long.

You don't need to use String (in fact it saves RAM and avoids memory fragmentation to not use it). You don't need to pass the length, with both char* and String you can deduce the length. If you use long as the return type you can handle larger numbers.

By using pow you are bringing in a library which is not needed and which will consume program memory. By using double you are introducing possible inaccuracies since double does not necessarily store numbers exactly. Your code used 7,604 bytes of program memory once I corrected the syntax error and added an empty setup function.


Also, the method I illustrate above is much faster. I timed it at converting "BA" in 4.3 µs, whereas the method using the pow function takes 442 µs. So the simpler method is also 100 times faster.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.