Меню
Что нового?

% для чисел > PHP_INT_MAX

dimagolov

Новичок
% для чисел > PHP_INT_MAX

Есть ф-я base62_encode для соответствующего кодирования чисел. Реализовано циклом с % 62 и последующим делением на 62. Пока кодируемое число вписывается в PHP_INT_MAX проблем нету. Но если число привысит это значение, то начнется преобразование во float, а не в int и даст не тот результат, что ожидался.
Понятно как отслеживать опасную ситуауию, if ($x > PHP_INT_MAX) intval($x) = PHP_INT_MAX, то есть в случае intval($x) != PHP_INT_MAX мы можем считать не опасаясь за переполнение.

Очевидным решением в случае больших чисел является bcmath. Вопрос в том, можно ли достаточно просто реализовать подобное без этого расширения?
 

dimagolov

Новичок
так точности ведь не хватит при кол-ве разрядов больше определенного.

по идее можно построить ряд чисел, кратных 62, которые больше 32-х битный PHP_INT_MAX и меньше, чем 2^64 (больше как бы не нужно) и по ним строковыми ф-ями считать...
а сколько таких чисел будет? блин, много :(

-~{}~ 22.10.09 19:20:

пока идея делить исходное число на "круглые" числа в 62-ричной системе чтобы потом просто делать конкатенацию получившихся частей.
 
Жигaн

Жигaн

Новичок
Я так понял, что числа представлены в десятичном виде и хранятся в строке? Тогда можно поделить в столбик :)

PHP: 
<?php
function ldiv($a, $b, &$mod = null) {
    $a = (string)$a;
    $b = (int)$b;
    $a_len = strlen($a);
    $result = '';
    $mod_b = abs($b);
    $delta = 0;

    for($idx = 0; $idx < $a_len;) {
        $left_part = $delta . $a[$idx++];

        for(; $left_part < $mod_b && $idx < $a_len; ++$idx) {
            $left_part .= $a[$idx];
            $result .= '0';
        }

        $delta = $left_part % $b;
        $result .= floor($left_part / $b);

        if($left_part < $mod_b) {
            break;
        }

    }

    $mod = $delta;

    return $result;
}

$num = '18446744073709551616'; // 2^64
$result = ldiv($num, 62, $mod);

var_dump($num, $result, $mod);
-~{}~ 23.10.09 02:53:

ldiv ессно надо использовать для чисел больших PHP_INT_MAX, далее переходить на %. Для 2^64 / 62 это шесть итераций.
 

dimagolov

Новичок
Сделал пока лежал сайт сам и деление (причем можно задавать делитель > PHP_INT_MAX) и base62. Свел в один класс.

PHP: 
if (!function_exists('is_bigint')) {
	function is_bigint($Value) {
		$Value= trim($Value, " \t\n\r");
		$trimmed= trim($Value, '+-0123456789');
		return (is_numeric($Value) && empty($trimmed));
	}
}

class Math {
	public static function base62_encode ($num) {
		if ($num === '' || !is_bigint($num))
			return FALSE;

	    $ni= intval($num);
		if ($ni < PHP_INT_MAX)
			return self::base62_encode_int($ni);

		$spliter= 916132832;
		$parts= self::divide_int($num, $spliter);
		$res= '';
		while ($parts[0] > 0) {
			$cur= self::base62_encode_int(intval($parts[1]));
			while (strlen($cur) < 5)
				$cur= '0'.$cur;
			$res= $cur.$res;
			$parts= self::divide_int($parts[0], $spliter);
		}
		return self::base62_encode_int(intval($parts[1])).$res;
	}

	public static function base62_decode ($str) {
	    $ret= 0;
	    for ($i= 0, $l= strlen($str); $i < $l; $i++) {
	        $cval= ord($str[$i]);
	        if (ctype_digit($str[$i]))
	            $cval-= ord('0');
	        elseif (ctype_upper($str[$i]))
	            $cval-= ord('A') - 10;
	        elseif (ctype_lower($str[$i]))
	            $cval-= ord('a') - 36;
	        else
	            return -1;
	        $ret= self::add62digit($ret, $cval);
	    }
	    return $ret;
	}

	public static function compare_int($a, $b) {
		if ($a === '' || $b === '' || !is_bigint($a) || !is_bigint($b))
			return FALSE;

		$ai= intval($a);
		$bi= intval($b);
		if ($ai < PHP_INT_MAX && $bi < PHP_INT_MAX)
			return $ai < $bi ? -1 : ($ai > $bi ? 1 : 0);

		$a= ltrim(trim($a, " \t\n\r"), '0');
		$b= ltrim(trim($b, " \t\n\r"), '0');

		$al= strlen($a);
		$bl= strlen($b);
		if ($al < $bl)
			return -1;
		else if ($al > $bl)
			return 1;
		for ($i= 0; $i < $al; $i++) {
			$ai= intval($a[$i]);
			$bi= intval($b[$i]);
			if ($ai < $bi)
				return -1;
			else if ($ai > $bi)
				return 1;
		}
		return 0;
	}

	public static function divide_int ($dividend, $divisor) {
		if ($dividend === '' || $divisor === '' || !is_bigint($dividend) || !is_bigint($divisor))
			return FALSE;

		$dividend= ltrim(trim($dividend, " \t\n\r"), '0');
		$divisor= ltrim(trim($divisor, " \t\n\r"), '0');

		$c= self::compare_int($dividend, $divisor);
		if ($c < 0)
			return array ('0', $dividend);
		else if (!$c)
			return array ('1', '0');

		$res= '';
		$dl= strlen($divisor);
		$cur= substr($dividend, 0, $dl);
		if (intval('9'.$divisor) < PHP_INT_MAX) {
			$divisor= intval($divisor);

			for ($i= 0, $l= strlen($dividend); $i + $dl <= $l; $i++) {
				$d= 0;
				if (intval($cur) >= $divisor) {
					$res.= (string)((int)($cur / $divisor));
					$cur= (string)($cur % $divisor);
				} else
					$res.= '0';
				if ($i + $dl < $l)
					$cur.= $dividend[i + dl];
			}
		} else {
			for ($i= 0, $l= strlen($dividend); $i + $dl <= $l; $i++) {
				$d= 0;
				$c= self::compare_int($cur, $divisor);
				while ($c >= 0) {
					for ($j= 0; $j < $dl; $j++) {
						$cl= strlen($cur);
						if ($cur[$cl - $j - 1] >= $divisor[$dl - $j - 1])
							$cur[$cl - $j - 1]= $cur[$cl - $j - 1] - $divisor[$dl - $j - 1];
						else {
							for ($k= $j + 1; $k < $cl; $k++)
								if ($cur[$cl - $k - 1] !== '0') {
									$cur[$cl - $k - 1]= $cur[$cl - $k - 1] - 1;
									break;
								} else
									$cur[$cl - $k - 1]= '9';
							$cur[$cl - $j - 1]= 10 + $cur[$cl - $j - 1] - $divisor[$dl - $j - 1];
						}
					}
					$d++;
					$c= self::compare_int($cur, $divisor);
				}
				$res.= (string)$d;
				if ($i + $dl < $l)
					$cur.= $dividend[$i + $dl];
			}
		}

		$res= ltrim($res, '0');
		$cur= ltrim($cur, '0');
		return array ($res ? $res : '0', $cur ? $cur : '0');
	}

	private static function base62_encode_int ($num) {
	    $ret= '';
	    while ($num >= 0) {
	    	$cval= $num % 62;
	    	if ($cval < 10)
	    		$ret.= chr(ord('0') + $cval);
	    	elseif ($cval < 36)
	    		$ret.= chr(ord('A') + $cval - 10);
	    	else
	    		$ret.= chr(ord('a') + $cval - 36);
	    	if ($num < 62)
	    		return strrev($ret);
 	   	else
 	   		$num= ($num - $val) / 62;
 	   }
	    return $ret;
	}

	private static function add62digit($num, $val) {
		if (intval($num) <= ((PHP_INT_MAX - 62) / 62))
			return (string)(intval($num) * 62 + intval($val));
	
		$ret= '';
		$num= (string)$num;
		$val= (string)$val;

		for ($i= 0, $cur= 0, $nl= strlen($num), $vl= strlen($val); $i <= $nl; $i++) {
			if ($i < $nl)
				$cur+= $num[$nl - $i - 1] * 2;
			if ($i < $vl)
				$cur+= $val[$vl - $i - 1];
			if ($i)
				$cur+= $num[$nl - $i] * 6;
			$ret= ($cur % 10).$ret;
			$cur= (int)($cur / 10);
		}
	
		if ($cur)
			$ret= $cur.$ret;
		return $ret;
	}
}
 
Войдите или зарегистрируйтесь для ответа.
Сверху