-2

I have a program that takes in anywhere from 20,000 to 500,000 velocity vectors and must output these vectors multiplied by some scalar. The program allows the user to set a variable accuracy, which is basically just how many decimal places to truncate to in the calculations. The program is quite slow at the moment, and I discovered that it's not because of multiplying a lot of numbers, it's because of the method I'm using to truncate floating point values.

I've already looked at several solutions on here for truncating decimals, like this one, and they mostly recommend DecimalFormat. This works great for formatting decimals once or twice to print nice user output, but is far too slow for hundreds of thousands of truncations that need to happen in a few seconds.

What is the most efficient way to truncate a floating-point value to n number of places, keeping execution time at utmost priority? I do not care whatsoever about resource usage, convention, or use of external libraries. Just whatever gets the job done the fastest.

EDIT: Sorry, I guess I should have been more clear. Here's a very simplified version of what I'm trying to illustrate:

import java.util.*;
import java.lang.*;
import java.text.DecimalFormat;
import java.math.RoundingMode;
public class MyClass {
    
    static class Vector{
        float x, y, z;
        @Override
        public String toString(){
            return "[" + x + ", " + y + ", " + z + "]";
        }
    }
    
    public static ArrayList<Vector> generateRandomVecs(){
      ArrayList<Vector> vecs = new ArrayList<>();
      Random rand = new Random();
      for(int i = 0; i < 500000; i++){
          Vector v = new Vector();
          v.x = rand.nextFloat() * 10;
          v.y = rand.nextFloat() * 10;
          v.z = rand.nextFloat() * 10;
          vecs.add(v);
      }
      return vecs;
    }
    
    public static void main(String args[]) {
        
    int precision = 2;
    
    float scalarToMultiplyBy = 4.0f;
   
     ArrayList<Vector> velocities = generateRandomVecs();
     
     System.out.println("First 10 raw vectors:");
     for(int i = 0; i < 10; i++){
         System.out.print(velocities.get(i) + " ");
     }
      
     /* 
     This is the code that I am concerned about
     */
     
     DecimalFormat df = new DecimalFormat("##.##");
     df.setRoundingMode(RoundingMode.DOWN);

     long start = System.currentTimeMillis();

     for(Vector v : velocities){
        /* Highly inefficient way of truncating*/
        v.x = Float.parseFloat(df.format(v.x * scalarToMultiplyBy));
        v.y = Float.parseFloat(df.format(v.y * scalarToMultiplyBy));
        v.z = Float.parseFloat(df.format(v.z * scalarToMultiplyBy));
     }
      
     long finish = System.currentTimeMillis();
     long timeElapsed = finish - start;
     
     System.out.println();
     System.out.println("Runtime: " + timeElapsed + " ms");
     
     System.out.println("First 10 multiplied and truncated vectors:");
     for(int i = 0; i < 10; i++){
         System.out.print(velocities.get(i) + " ");
     }
    }
}

The reason it is very important to do this is because a different part of the program will store trigonometric values in a lookup table. The lookup table will be generated to n places beforehand, so any velocity vector that has a float value to 7 places (i.e. 5.2387471) must be truncated to n places before lookup. Truncation is needed instead of rounding because in the context of this program, it is OK if a vector is slightly less than its true value, but not greater.

Lookup table for 2 decimal places:
...
8.03 -> -0.17511085919
8.04 -> -0.18494742685
8.05 -> -0.19476549993
8.06 -> -0.20456409661
8.07 -> -0.21434223706
...

Say I wanted to look up the cosines of each element in the vector {8.040844, 8.05813164, 8.065688} in the table above. Obviously, I can't look up these values directly, but I can look up {8.04, 8.05, 8.06} in the table.

What I need is a very fast method to go from {8.040844, 8.05813164, 8.065688} to {8.04, 8.05, 8.06}

Thicc
  • 195
  • 1
  • 1
  • 5
  • 1
    You need to show us your existing code and explain how you determined it's the truncation that is the problem. Without that, we are just guessing. Please (re)read [ask]. – Jim Garrison Oct 17 '21 at 04:16
  • What sort of precision are you expecting? With floats, you're not likely to get perfect decimal precision anyway, but you're likely to get accumulating inaccuracy. – Louis Wasserman Oct 17 '21 at 04:23
  • 2
    There is no such thing as rounding or truncating floating-point to a specific number of decimal places. FP has binary places, not decimal places, and the two are incommensurable. I suggest you carry round all the precision you can until it comes time to *display* or *print* the values in base-10, at which point it becomes trivial to round or truncate as you wish. – user207421 Oct 17 '21 at 04:25
  • @user207421 is probably right: it'll be most efficient and most accurate _anyway_ to not do any truncation whatsoever. What's the point of lowering accuracy for zero benefit? – Louis Wasserman Oct 17 '21 at 04:27
  • This question does _not_ seem like a duplicate of that question, at least; it specifically cites the answer to the marked duplicate as insufficient. – Louis Wasserman Oct 17 '21 at 04:51
  • 1
    If this is a stand-alone program, I expect that the real reason it is "quite slow at the moment" is a combination of factors. Other factors will / could include the overheads of reading and writing the data, and JVM startup / warmup overheads. Have you **profiled** your code to determine where the bottlenecks really are? (Or is your "discovery" actually a just a guess that truncation is the bottleneck?) – Stephen C Oct 17 '21 at 05:17
  • @LouisWasserman My answer in the duplicate refutes the feasibility of the problem. You are referring to another question altogether. – user207421 Oct 17 '21 at 05:22
  • I have updated the post with some sample code. Sorry if I was not clear. – Thicc Oct 17 '21 at 05:30
  • Basically what I need to do is convert every float value which could be any number of decimal places into a value that is truncated to n places (i.e. 1.2345678 becomes 1.23) after being multiplied by a scalar. I'm trying to do upwards of 1 million truncations in a short period of time. – Thicc Oct 17 '21 at 05:32
  • 2
    Don't try to use floats as keys in a lookup table (unless you are happy to do a binary search, in which case no need to truncate) Use integers, and at the point at which you do your lookup, multiply the number by 100 and truncate to an integer. – tgdavies Oct 17 '21 at 06:55
  • The lookup table is already optimized using a node structure (it's not even written in Java). I'm not responsible for that part of the code, but I believe it is something like an array indexed for each digit 0-9 and index 10 for decimal point, then each element points to another array containing 10 digits/DP, etc. The table reads in a stream of floating point values bit by bit, so extracting the digits one by one is very fast. Looking up 2.34, for example, would be something like table[2][10][3][4]. So it's just O(# of digits) access time. Again, I'm not too sure on the details of that. – Thicc Oct 17 '21 at 07:14
  • 1
    "Looking up 2.34, for example, would be something like `table[2][10][3][4]`." This sounds terribly inefficient (especially extracting `2`, `10`?, `3` and `4` first). As @tgdavies suggested, you should just do something like `table[(int)(x*100)]`. – chtz Oct 17 '21 at 08:48
  • Re “Truncation is needed instead of rounding because in the context of this program, it is OK if a vector is slightly less than its true value, but not greater”: Change the generation of the lookup table so that the value in the table for index k is the value of f(x) for x equal to the largest floating-point value that produces index k when the index is computed with rounding, where f is the desired mathematical function. Then there will be no need for truncation. – Eric Postpischil Oct 17 '21 at 11:34
  • 2
    Re “… it is OK if a vector is slightly less than its true value, but not greater”: This is dubious. The sample cosine entries you show are several cycles past the origin; the wave has gone up and down several times. A computed number less than the ideal number could produce a cosine either less than or greater the ideal cosine depending on where in the cycle it falls. This points to an X-Y problem: You have some prior problem to solve, have decided upon a solution, and are asking us how to implement the solution. But it is not a good solution; you should reconsider the original problem. – Eric Postpischil Oct 17 '21 at 11:43

1 Answers1

1

The fastest way, which will introduce rounding error, is going to be to multiply by 10^n, call Math.rint, and to divide by 10^n.

That's...not really all that helpful, though, considering the introduced error, and -- more importantly -- that it doesn't actually buy anything. Why drop decimal points if it doesn't improve efficiency or anything? If it's about making the values shorter for display or the like, truncate then, but until then, your program will run as fast as possible if you just use full float precision.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • This isn't for display purposes. The truncation is needed for internal trigonometric lookups in a table that only supports up to some arbitrary number of places. For example, a trig lookup table that goes from -5 to 5 with 2 decimal places would contain entries for [-5, -4.99, -4.98 ... 4.98, 4.99, 5]. The raw velocity vectors, however, can have floating point components that go to more than 2 decimal places (i.e. 3.4731345). The table would not contain an entry for 3.4731345, but it would contain one for 3.47. I need code that can turn 3.4731345 into 3.47 very quickly. – Thicc Oct 17 '21 at 05:37
  • Then do the thing I described above. Don't expect the divided number to be exactly 3.47, though. – Louis Wasserman Oct 17 '21 at 16:20