factorize.cpp

Go to the documentation of this file.

// Copyright (c) 2024 anabrid GmbH
// Contact: https://www.anabrid.com/licensing/
//
// SPDX-License-Identifier: MIT OR GPL-2.0-or-later
 
#include "utils/factorize.h"
 
#include <Arduino.h> //
#include <math.h>
 
 
std::pair<unsigned long long, unsigned long long> utils::factorize(unsigned long long input,
                                                                   unsigned int acceptable_delta) {
  unsigned long long root = sqrt(input);
  if (root * root > input - acceptable_delta)
    return std::make_pair(root, root);
 
  unsigned long long x = root, y = root;
 
begin:
  if (x * y > input + acceptable_delta) {
    y--;
    x = input / y;
    goto begin;
  } else if (x * y < input - acceptable_delta) {
    x++;
    y = input / x;
    goto begin;
  } else
    return std::make_pair(x, y);
}
 
 
bool utils::factorize3(uint64_t n, uint32_t &a, uint32_t &b, uint32_t &c) {
  constexpr uint64_t MAX16 = 0xFFFFu;
  if (n <= MAX16 * MAX16) {
    auto f = utils::factorize(n);
    a = f.first; b = f.second; c = 1;
    return a <= MAX16 && b <= MAX16;
  }
  c = (uint32_t)((n + MAX16 * MAX16 - 1) / (MAX16 * MAX16));
  if (c > MAX16) return false;
  uint64_t ab = (n + c - 1) / c;  // ceil(n/c)
  auto f = utils::factorize(ab);
  a = f.first; b = f.second;
  return a <= MAX16 && b <= MAX16;
}